[Java] 백준 BOJ / 14503번: 로봇청소기

로봇청소기

문제

---

문제 설명

로봇 청소기의 좌표 r,c 가 주어지고 방의 크기와 방의 정보가 주어지면 로봇청소기의 청소 순서에 따라 청소를 하고 청소를 할 수 없을 때까지 청소한 칸의 개수를 세는 문제이다.

로봇청소기의 조건은 아래와 같다.

1. 처음 빈칸은 청소되어 있지 않다.
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈칸이 없는 경우 후진가능하면 후진하고 불가능하면 종료한다.
3. 현재 칸의 주변 4칸 중 청소되지 않은 빈칸이 있는 경우 반시계로 90도 회전하여 전진한다.
4. 처음 바라보는 방향이 0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽을 바라보고 있다.

문제에서 주의해야할 점은 로봇청소기가 반시계 방향으로 회전한다는 점이다.

---

구현

일단 dx 배열과 dy 배열을 선언하는 부분부터 봐야한다.

문제의 초기 조건에서의 북, 동, 남, 서의 방향을 정해주기 위해서는 아래와 같이 선언해야 한다.

static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};

방향 (dir)	dx 값 (행 변화)	dy 값 (열 변화)	설명
0 (북)	-1 (위로 이동)	0 (변화 없음)	한 칸 위로 이동
1 (동)	0 (변화 없음)	1 (오른쪽 이동)	한 칸 오른쪽 이동
2 (남)	1 (아래로 이동)	0 (변화 없음)	한 칸 아래로 이동
3 (서)	0 (변화 없음)	-1 (왼쪽 이동)	한 칸 왼쪽으로 이동

이렇게 선언한 dx, dy 배열과 초기에 입력받은 좌표 r,c에서 DFS를 시작하면 된다.

처음에 입력받은 x,y 좌표를 방문했으니 해당 좌표를 청소를 했다는 뜻으로 -1로 초기화를 한 후에 방향을 정해준다.

이제 주변 4칸을 둘러봐야하는데 청소되지 않은 빈칸이 있는 경우 반시계 방향으로 회전을 해야한다.

현재 dx 배열과 dy 배열은 북, 동, 남 ,서의 방향으로 선언이 되어있기 때문에 반시계방향으로 돌리려면 아래와 같은 과정이 필요하다.

현재 방향 (dir)	반시계 회전 후(new dir)
0 (북)	3 (서)
1 (동)	0 (북)
2 (남)	1 (동)
3 (서)	2 (남)

이렇게 변하기 위해서 식을 일반화 하면 아래의 식이 나오게 된다.

dir = (dir + 3) % 4;

따라서 새로 정한 dir 값으로 그래프를 탐색하고 만약 해당 좌표의 값이 0이면 다시 DFS를 하면 된다.

위의 조건에서 걸리지 않았다면 근처에 청소할 곳이 없고 후진을 해야한다. 후진은 현재 보고 있는 방향의 반대이니 dir에 3 이 아닌 2를 더해주고 모듈러 연산을 해주면 된다.

완성된 코드는 아래와 같다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 1은 벽이고 0은 빈칸
 * 1. 청소 안됐으면 청소
 * 2. 주변 4칸 중 청소되지 않은 빈칸이 없는 경우
 *      1. 바라보는 방향을 유지한 채로 한칸 후진할수 있으면 후진하고 1번으로 돌아감
 *      2. 바라보는 방향의 뒤쪽 칸이 벽이 후진할 수 없다면 작동을 멈춘다.
 *      3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
 *          1. 반시계 방향으로 90도 회전
 *          2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
 *          3. 1번으로 돌아간다.
 */
public class Main_14503 {
    static int n, m;
    static int r, c, d;
    static int[][] arr;
    static boolean[][] visit;
    //북, 동, 남, 서
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int count = 1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n][m];
        visit = new boolean[n][m];

        st = new StringTokenizer(br.readLine());

        //초기 로봇청소기 좌표 r, c
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        //북, 동, 남, 서 (0, 1, 2, 3)
        d = Integer.parseInt(st.nextToken());

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(r, c, d);

        System.out.println(count);
    }

    public static void dfs (int x, int y, int dir) {
        //청소
        arr[x][y] = -1;

        for (int i = 0; i < 4; i++) {
            dir = (dir + 3) % 4;

            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                if (arr[nx][ny] == 0) {
                    count++;
                    dfs(nx, ny, dir);
                    return;
                }
            }
        }

        //후진
        int d = (dir + 2) % 4;
        int bx = x + dx[d];
        int by = y + dy[d];
        if (bx >= 0 && bx < n && by >= 0 && by < m && arr[bx][by] != 1) {
            dfs(bx, by, dir);
        }
    }
}