청소는 즐거워 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

💡  풀이 방식

• 구현, 시뮬레이션

1. 먼지 비율을 배열로 미리 저장해두기 (추가될 먼지양 계산용)

2. 방향이 왼쪽/오른쪽으로 바꼈을 때, 동일한 방향에 대해 이동거리 +1

(단, 마지막 부분은 그렇지 않음)

if(dir == 0 || dir == 2) {
	moveNum++;
}

 

 

3. 이동하면서 먼지 비율 배열 값을 활용해 현재 위치의 먼지양에 각 비율을 곱함

(최종적으로 남은 먼지양을 따로 계산해 처리해야 함)

 

 

 

💥 유의사항

마지막 부분 별도 처리 !

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0, 1, 0, -1}; // 회전 방향 : 서남동북
    static int[] dy = {-1, 0, 1, 0};
 
    static int N;
 
    static int x, y;
    static int dir, moveNum; // 이동 방향, 이동 거리
 
    static int ans;
 
    static int[][] grid;
 
    // 먼지 비율 
    static int[][][] dustRatio = new int[][][] {
        {
            {0, 0, 2, 0, 0},
            {0, 10, 7, 1, 0},
            {5, 0, 0, 0, 0},
            {0, 10, 7, 1, 0},
            {0, 0, 2, 0, 0},
        },
        {
            {0, 0, 0, 0, 0},
            {0, 1, 0, 1, 0},
            {2, 7, 0, 7, 2},
            {0, 10, 0, 10, 0},
            {0, 0, 5, 0, 0},
        },
        {
            {0, 0, 2, 0, 0},
            {0, 1, 7, 10, 0},
            {0, 0, 0, 0, 5},
            {0, 1, 7, 10, 0},
            {0, 0, 2, 0, 0},
        },
        {
            {0, 0, 5, 0, 0},
            {0, 10, 0, 10, 0},
            {2, 7, 0, 7, 2},
            {0, 1, 0, 1, 0},
            {0, 0, 0, 0, 0},
        }        
    };
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        grid = new int[N][N];
 
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        x = N/2;
        y = N/2;
        dir = 0;
        moveNum = 1;    // 이동 거리 🔔
 
        while(!end()) {
            for(int i = 0 ; i < moveNum ; i++) {
                move();
 
                if(end()) { // 좌측 최상단에 도착하면 종료
                    break;
                }
            }
 
            dir = (dir + 1) % 4;
            if(dir == 0 || dir == 2) { // 🔔 왼쪽/오른쪽일 때, 동일한 방향에 대해 이동거리 +1
                moveNum++;
            }            
        }
 
        System.out.println(ans);
    }
 
    private static boolean end() {
        return (x == 0 && y == 0);
    }
 
    // 청소하는 메소드
    private static void move() {
        x += dx[dir];
        y += dy[dir];
 
        // 현재 위치 기준 각 위치에 먼지 더하기
        int addedDust = 0;
        for(int i = 0 ; i < 5 ; i++) {
            for(int j = 0 ; j < 5 ; j++) {
                int dust = grid[x][y] * dustRatio[dir][i][j] / 100;
                addDust(x + i - 2, y + j - 2, dust);
 
                addedDust += dust;
            }
        }
 
        // a% 자리에 먼지 추가하기
        addDust(x + dx[dir], y + dy[dir], grid[x][y] - addedDust);
    }
 
    // (a, b) 위치에 dust만큼 먼지 추가
    private static void addDust(int a, int b, int dust) {
        if(!inRange(a, b))  ans += dust;            // 격자 범위 벗어나면, 답에 더함
        else                grid[a][b] += dust;     // 격자 범위 안이면, 칸에 더함
    }
 
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < N && 0 <= y && y < N );
    }
}

 

---

💦 어려웠던 점

와우... 비율 계산하는 게 어렵네..

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리 &  백준 20057 마법사 상어와 토네이도

20057번: 마법사 상어와 토네이도