[Baekjoon] 14503번: 로봇 청소기

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

14503번: 로봇 청소기

문제 설명

주어진 조건대로 동작하는 시뮬레이션 문제이다. 문제를 잘 읽고 알고리즘을 구현해야 한다. 특별히 부연설명할 게 없어서 설명은 사이트를 참고하면 좋겠다.

풀이 방법

주어진 조건대로 구현하면 되는 심플한 문제이다. 대신 조건이 많아서 꼼꼼히 예외처리를 해줘야 한다. 필자는 큐를 활용해서 해결했다. BFS를 약간 변형했다.

코드를 읽어내려가면 자연스럽게 이해되므로 코드를 보도록 하자.

import java.io.*;
import java.util.*;

class Main {

    static int N, M;
    static int ans;
    static int[] dx = {-1, 0, 1, 0}; // 북 동 남 서
    static int[] dy = {0, 1, 0, -1};
    static int[][] room;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] split = br.readLine().split(" ");
        N = Integer.parseInt(split[0]);
        M = Integer.parseInt(split[1]);

        split = br.readLine().split(" ");
        int startX = Integer.parseInt(split[0]);
        int startY = Integer.parseInt(split[1]);
        int startDirection = Integer.parseInt(split[2]);

        room = new int[N][M];

        for (int i = 0; i < N; i++) {
            int[] roomDetail =
                    Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int j = 0; j < M; j++) {
                room[i][j] = roomDetail[j];
            }
        }

        operateRobot(startX, startY, startDirection);

        System.out.println(ans);
    }

    private static void operateRobot(int x, int y, int direction) {
        Queue<Coordinate> q = new LinkedList<>();
        q.offer(new Coordinate(x, y, direction));

        while (!q.isEmpty()) {
            Coordinate c = q.poll();

            // 1. 현재 칸이 아직 청소하지 않은 경우, 현재 칸을 청소한다.
            if (room[c.x][c.y] == 0) {
                room[c.x][c.y] = 2; // 청소했음을 2로 나타낸다.
                ans++;
            }

            // 2. 현재 칸의 주변 4칸 확인
            boolean existNotClean = false;
            for (int i = 0; i < 4; i++) {
                int nextX = c.x + dx[i];
                int nextY = c.y + dy[i];

                // 한 칸이라도 청소하지 않았다면 청소할 곳이 있으므로
                // 체크 후 바로 for 문을 빠져나온다.
                if (room[nextX][nextY] == 0) {
                    existNotClean = true;
                    break;
                }
            }

            if (existNotClean) {
                int curDir = c.d;
                for (int i = 1; i <= 4; i++) {
                    int nextDir = (curDir + 4 - i) % 4;
                    int nextX = c.x + dx[nextDir];
                    int nextY = c.y + dy[nextDir];
                    if (room[nextX][nextY] == 0) {
                        q.offer(new Coordinate(nextX, nextY, nextDir));
                        break; // break하지 않으면 로봇이 복제가 되는거나 마찬가지
                    }
                }
            } else {
                int curDir = c.d;

                int nextX = c.x - dx[curDir];
                int nextY = c.y - dy[curDir];

                // 후진을 못하면 동작 멈춤
                if (room[nextX][nextY] == 1)
                    break;

                // 후진
                q.offer(new Coordinate(nextX, nextY, curDir));
            }
        }
    }

    static class Coordinate {
        int x;
        int y;
        int d;

        public Coordinate(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
}

보통 2차원 배열 탐색 시 범위 초과에 대한 예외 처리를 하는데 이 문제의 경우 입력 자체를 벽으로 감싸서, 즉 1로 둘러싼 형태로 제공해주기 때문에 별다른 예외처리가 필요하지 않았다.