백준 - 14503번(로봇 청소기)

문제 출처: https://www.acmicpc.net/problem/14503

문제

• 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

• 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 북쪽에서부터 r번째, 서쪽에서부터 c번째로 위치한 칸은 (r, c)로 나타낼 수 있다.

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

  1. 현재 위치를 청소한다.
  2. 현재 위치에서 다음을 반복하면서 인접한 칸을 탐색한다.
     a. 현재 위치의 바로 왼쪽에 아직 청소하지 않은 빈 공간이 존재한다면, 왼쪽 방향으로 회전한 다음 한 칸을 전진하고 1번으로 돌아간다. 그렇지 않을 경우, 왼쪽 방향으로 회전한다. 이때, 왼쪽은 현재 바라보는 방향을 기준으로 한다.
     b. 1번으로 돌아가거나 후진하지 않고 2a번 단계가 연속으로 네 번 실행되었을 경우, 바로 뒤쪽이 벽이라면 작동을 멈춘다. 그렇지 않다면 한 칸 후진한다.

package baekjoon.no14503;

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

public class Main {

    private static final int[][] directions = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }, };

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

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        int N = Integer.parseInt(tokenizer.nextToken());    // 세로(행)
        int M = Integer.parseInt(tokenizer.nextToken());    // 가로(열)

        tokenizer = new StringTokenizer(reader.readLine());

        int r = Integer.parseInt(tokenizer.nextToken());    // 청소기 위치(행)
        int c = Integer.parseInt(tokenizer.nextToken());    // 청소기 위치(열)
        int currDir = Integer.parseInt(tokenizer.nextToken());  // 처음 방향

        int[][] arr = new int[N][M];
        boolean[][] visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(tokenizer.nextToken());
            }
        }

        int ans = 0;

        Outer: while (true) {
            // 일단 청소
            if (!visited[r][c]) {
                ans++;
                visited[r][c] = true;
            }

            // 일단 3번 돌려보고 이 안에 빈칸이 있으면 전진한다.
            // 0이면 이동 가능, 1이면 불가
            for (int i = 1; i <= 4; i++) {
                int temp = currDir - i;
                if (temp < 0) temp += 4;
                int dy = r + directions[temp][0];
                int dx = c + directions[temp][1];

                if (dy >= 0 && dy < N && dx >= 0 && dx < M) {
                    if (arr[dy][dx] == 0 && !visited[dy][dx]) { // 빈 공간을 찾은 경우
                        r = dy;
                        c = dx; // 전진 처리
                        currDir = temp;
                        continue Outer;
                    }
                }
            }

            // 더 이상 갈 곳이 없는 경우
            int dy = r - directions[currDir][0];
            int dx = c - directions[currDir][1];

            if (dy >= 0 && dy < N && dx >= 0 && dx < M) {
                if (arr[dy][dx] == 0) { // 뒤가 빈칸인 경우 뒤로 한칸 이동
                    r = dy;
                    c = dx;
                } else {
                    break;
                }
            }
        }

        System.out.println(ans);
    }

}

• 주어진 조건에 맞게 문제를 풀면 되는 "시뮬레이션" 문제이다.
• 처음에 문제 조건을 잘못 이해하여 약간 시간이 소모되었다.
• "2a번 단계가 연속 4번 실행된 경우" 라고 하였는데, 결국 그 자리에서 4번을 살핀 후 그래도 답이 안나오면 2b 단계를 실행하기 때문에 사실상 5번째에 이 로직을 처리해야한다. 이를 4번째에 처리하게 하여 계속 실패하였다...
• 그 다음, 계속 실패가 떠서 질문을 참조하는데 2차원 배열에서 델타를 참조할 때의 범위를 확인하라는 말이 조금 나왔었다. 설마 그 부분을 틀렸을까 생각하고 코드를 다시 보는 순간, y좌표와 x좌표 둘 다 N값으로 크기를 확인하고 있었다...😞😞
• 그래도 생각보다 짧은 시간에 풀 수 있어서 뿌듯하다. 처음에는 재귀함수로 풀었으나 그대로 반복문으로 옮겼고, 8ms 정도 이득을 보았다.