[BOJ] 14503. 로봇청소기

 

 

문제

 

 

 

 

 

풀이

 

 

4방향으로 탐색하며 인접한 칸 중 방문이 가능한 칸으로 이동하는 것을 보아 백준의 2178 미로찾기 문제와 비슷한 유형이라는 생각이 들었다. (BFS나 DFS로 풀이가 가능할 조짐이 보임.) 그러나 아래와 같은 추가적인 고려 사항이 있다.

 

1. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는  경우

• 반시계 방향으로 90도 회전
• 바라보는 방향 기준 앞쪽 칸이 청소되지 않은 경우, 한 칸 전진

=> 큐에서 받아온 방향을 기준으로 반시계 방향 회전한 방향으로의 좌표를 구해 이동한다

 

ex) 위 문제에서 주어진 방향값은 0(북), 3(서), 2(남), 1(동) 이다.

만약 현재 방향이 0(북)이고, 반시계 방향으로 회전한다면 아래와 같이 반복된다. (순환)

 

0(북) -> 3(서) -> 2(남) -> 1(동) -> 0(북) 

 

방향은 0, 1, 2, 3의 4가지 값을 순환해야 하므로, 숫자가 음수가 되는 경우를 처리해야 한다.

따라서 나머지 연산으로 음수를 방지하고, 위 4가지 값의 범위 내에서 순환하도록 해야한다.

 

방향이 반시계 방향으로 순환하며 이동하는 값을 도출하기 위해 아래와 같은 식이 세워진다.

 

0(북) -> 3(서) => 3%4 = 3

3(서) -> 2(남) => 3+3%4 = 2

2(남) -> 1(동) => 2+3%4 = 1

1(동) -> 0(북) => 1+3%4 = 0

 

 

 

 

2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는  경우

• 바라보는 방향을 유지한 채로 한 칸 후진
• 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없으면 작동 멈춤

 

현재 칸에서 4방향 전부 방문이 불가능한 경우(코드에서는 isCleaned로 구분하였다), 후진한 좌표를 구하여 바라보는 방향을 유지한 채로 큐에 추가한다.

 

후진의 경우에도, 위 그림과 같이 (dir+2)%4라는 식을 세워 후진 방향을 구했다.

 

 

BFS 풀이

 

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

public class BOJ14503_BFS {
    static int N, M, r, c, d;
    static boolean[][] visited;
    static int[][] arr;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -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());

        visited = new boolean[N+1][M+1];
        arr = new int[N][M];

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

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        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());
            }
        }
        System.out.println(BFS());
    }

    public static int BFS() {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {r, c, d});
        // 청소한 칸의 갯수
        int cleaned = 1;
        // 현재 칸 청소
        visited[r][c] = true;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            boolean isCleaned = false;
            int x = curr[0];
            int y = curr[1];
            int dir = curr[2];

            for (int i=0; i<4; i++) {
                // 반시계 방향 회전
                dir = (dir + 3) % 4;
                int dx = x + dr[dir];
                int dy = y + dc[dir];
                // 청소기 방향
                // 반시계 방향 회전

                // 방문 조건 : 방문 가능 범위 내에서 다음 이동하는 칸이 아직 방문 및 청소하지 않은 곳
                if (dx >= 0 && dx < N && dy >= 0 && dy < M && !visited[dx][dy] && arr[dx][dy] == 0) {
                    // 청소
                    visited[dx][dy] = true;
                    cleaned++;
                    queue.add(new int[] {dx, dy, dir});
                    isCleaned = true;
                    // 이동하면 후진하므로 중지
                    break;
                }
            }

            // 4 방향 모두 청소가 불가능한 경우 (이미 청소 완료 or 벽)
            if (!isCleaned) {
                // 후진 (현재 방향의 반대)
                int backDir = (dir + 2) % 4;
                int bx = x + dr[backDir];
                int by = y + dc[backDir];

                // 후진 조건 : 이동 범위 내에 있고, 바라보는 방향의 뒤쪽 칸이 벽이 아닌 경우
                if (bx >= 0 && bx < N && by >= 0 && by < M && arr[bx][by] == 0) {
                    // 방향 그대로 유지한 채로 후진
                    queue.add(new int[] {bx, by, dir});
                }
            }
        }
        return cleaned;
    }
}

 

 

 

DFS 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.ref.Cleaner;
import java.util.StringTokenizer;

public class BOJ14503_DFS {
    static int N, M, r, c, d;
    static int[][] map;
    static boolean[][] visited;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    static int cleaned = 0;
    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());

        map = new int[N][M];
        visited = new boolean[N][M];

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

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());

        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        cleaned = 0;
        DFS(r, c, d);
        System.out.println(cleaned);
    }

    public static void DFS(int x, int y, int dir) {
        if (!visited[x][y]) {
            visited[x][y] = true;
            cleaned++;
        }

        for (int i = 0; i < 4; i++) {
            // 반시계 방향으로 회전
            dir = (dir + 3) % 4;
            int dx = x + dr[dir];
            int dy = y + dc[dir];

            // 조건: 범위 내 && 방문하지 않은 곳 && 벽이 아닌 곳
            if (dx >= 0 && dx < N && dy >= 0 && dy < M && !visited[dx][dy] && map[dx][dy] == 0) {
                DFS(dx, dy, dir);
                // 이동했으면 더 이상 탐색하지 않음
                return;
            }
        }

        int backDir = (dir + 2) % 4;
        int bx = x + dr[backDir];
        int by = y + dc[backDir];

        // 후진 조건: 벽이 아닌 경우 후진
        if (bx >= 0 && bx < N && by >= 0 && by < M && map[bx][by] == 0) {
            DFS(bx, by, dir); // 후진하면서 방향 유지
        }
    }
}

 

 

 

 

주의사항

 

반시계 방향으로 회전한 좌표값을 구하는 과정에서 다음과 같은 실수를 하여 애를 먹은 경험이 있다. (수작업으로 이동하는 방향까지 체크하며..) 

 

뭐가 잘못되었는지 아실까요?

while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            boolean isCleaned = false;
            int dx = curr[0];
            int dy = curr[1];
            int dir = curr[2];

            for (int i=0; i<4; i++) {
            	// 반시계 방향 회전
                dir = (dir + 3) % 4;
                dx = dx + dr[newDir];
                dy = dy + dc[newDir];

.
.
.

 

 

바로 반시계 방향으로 회전한 좌표값을 구할 때, 값을 누적해서 업데이트하는 방식 때문이었다.

위 코드에서는 dx와 dy가 반복문 안에서 누적되어 값이 이상해지는 문제가 있었다. 이 때문에 반복문 내부에서는 dx와 dy를 매번 새로 계산해야 한다. 아래와 같이 수정하여 오류를 해결하였다.

 while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            boolean isCleaned = false;
            int x = curr[0];
            int y = curr[1];
            int dir = curr[2];

            for (int i=0; i<4; i++) {
                // 반시계 방향 회전
                dir = (dir + 3) % 4;
                int dx = x + dr[dir];
                int dy = y + dc[dir];
                
          .
          .
          .