[JAVA] 백준 (골드5) 14503번 로봇 청소

링크

https://www.acmicpc.net/problem/14503

---

문제 설명

정답률 53.685%
로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 방은 $N \times M$ 크기의 직사각형으로 나타낼 수 있으며, $1 \times 1$ 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표
$(r, c)$로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 $(0, 0)$, 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 $(N-1, M-1)$이다. 즉, 좌표
$(r, c)$는 북쪽에서 $(r+1)$번째에 있는 줄의 서쪽에서 $(c+1)$번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.

로봇 청소기는 다음과 같이 작동한다.

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 $4$칸 중 청소되지 않은 빈 칸이 없는 경우,
   1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 $4$칸 중 청소되지 않은 빈 칸이 있는 경우,
   1. 반시계 방향으로 $90^\circ$ 회전한다.
   2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3. 1번으로 돌아간다.

---

입력 예제

3 3
1 1 0
1 1 1
1 0 1
1 1 1

---

출력 예제

1

---

풀이

문제 조건을 간단히 하면 다음과 같다.

1. 현재 칸 청소
2. 주변에 청소되지 않은 칸이 있을 경우
   1. 반시계 방향 회전 -> 청소되지 않은 칸이면 전진
3. 주변을 모두 청소한 경우
   1. 방향을 유지한 채로 후진
   2. 벽이라 후진할 수 없다면 중지

BFS를 이용해서 탐색한다. 방향은 0, 1, 2, 3이 북, 동, 남, 서를 의미하므로 다음과 같이 방향 배열을 생성한다.

int[] dr = {-1, 0, 1, 0};
int[] dc = {0, 1, 0, -1};

우선 현재 위치는 무조건 청소돼야 하므로 방문 처리를 해준 뒤 카운트한다.

//현재 위치 청소
if (!visited[curR][curC]) {
    visited[curR][curC] = true;
    count++;
}

그리고 주변의 모든 칸들의 청소 유무는 어짜피 모든 칸을 탐색하면서 청소가 안된 칸이 있을 때 반시계 방향으로 회전을 해야하므로 반시계 방향으로 탐색한다.
북 -> 서 -> 남 -> 동 이므로 0, 3, 2, 1순이 되어야 한다. 그리고 청소하지 않은 칸이 존재하면 큐에 추가하여 전진 처리한다.

for (int i = 0; i < 4; i++) {
    //반시계 방향으로 탐색
    dir = (dir + 3) % 4;
    int nextR = curR + dr[dir];
    int nextC = curC + dc[dir];
    //벽이면 패스
    if (map[nextR][nextC] == 1) {
        continue;
    }
    //청소하지 않았을 경우
    if (!visited[nextR][nextC]) {
        isClean = false;
        //반시계 방향으로 전진
        queue.add(new int[]{nextR, nextC});
        break;
    }
}

만약 모든 칸이 청소된 경우는 현 방향은 유지한 채 큐에 추가하여 후진 처리를 한다. 벽을 만났을 경우 중단한다.

//주변이 모두 청소된 상태일 경우
if (isClean) {
    //방향은 유지한 채 후진
    int nextR = curR - dr[dir];
    int nextC = curC - dc[dir];
    int next = map[nextR][nextC];
    //벽이 아니면 후진
    if (next == 0) {
        queue.add(new int[]{nextR, nextC});
    } else {
        break;
    }
}

코드

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

//백준
public class Main {

    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    static int[][] map;
    static boolean[][] visited;
    static int dir;
    static int count = 0;

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M];  //청소 여부 저장

        st = new StringTokenizer(br.readLine());
        int[] start = new int[2];
        start[0] = Integer.parseInt(st.nextToken());
        start[1] = Integer.parseInt(st.nextToken());
        dir = 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());
            }
        }
        bfs(start);

        System.out.println(count);
    }

    static void bfs(int[] start) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(start);

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int curR = cur[0];
            int curC = cur[1];
            //현재 위치 청소
            if (!visited[curR][curC]) {
                visited[curR][curC] = true;
                count++;
            }

            boolean isClean = true;

            for (int i = 0; i < 4; i++) {
                //반시계 방향으로 탐색
                dir = (dir + 3) % 4;
                int nextR = curR + dr[dir];
                int nextC = curC + dc[dir];
                //벽이면 패스
                if (map[nextR][nextC] == 1) {
                    continue;
                }
                //청소하지 않았을 경우
                if (!visited[nextR][nextC]) {
                    isClean = false;
                    //반시계 방향으로 전진
                    queue.add(new int[]{nextR, nextC});
                    break;
                }
            }

            //주변이 모두 청소된 상태일 경우
            if (isClean) {
                //방향은 유지한 채 후진
                int nextR = curR - dr[dir];
                int nextC = curC - dc[dir];
                int next = map[nextR][nextC];
                //벽이 아니면 후진
                if (next == 0) {
                    queue.add(new int[]{nextR, nextC});
                } else {
                    break;
                }
            }

        }
    }
}