[백준 14503] 로봇 청소기

로봇청소기

문제

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

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

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

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

아이디어

1. 현재칸 청소되지 않은 경우 → 청소하고 cnt+1
2. 4방향 모두 청소된 경우

• 바라보는 방향 유지, 뒤로 한칸 가능 ⇒ 1번
• 바라보는 방향 유지, 뒤로가기 불가능 ⇒ 종료

1. 4방향 중 청소 안된 부분 있는 경우

• 반시계 회전
• 바라보는 방향 청소 안된 경우 ⇒ 전진 ⇒ 1번

1. 종료가 될때까지 반복

첫번째 코드 - 실패(1%)

1. 반시계 방향 회전이고 idx는 시계 방향인 상황
2. 방향을 착각해서 시계 방향으로 돌림

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

public class Main {
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, -1, 0, 1 };
    static int N, M, r, c, d;
    static int[][] map;

    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());

        st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());

        map = new int[N][M];

        int cnt = 0;

        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());
            }
        }

        while (true) {
            if (map[r][c] == 0) { // 현재 칸 청소
                map[r][c] = 2;
                cnt++;
            }

            boolean flag = true;

            for (int i = 1; i <= 4; i++) {
                int k = d + i;
                if (k >= 4) {
                    k %= 4;
                }

                int nx = r + dx[k];
                int ny = c + dy[k];

                if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                    continue;

                if (map[nx][ny] == 0) {
                    d = k;
                    r = nx;
                    c = ny;
                    flag = false;

                    break;
                }
            }

            if (flag) {
                int nx = r + dx[d] * -1;
                int ny = c + dy[d] * -1;

                if (nx < 0 || ny < 0 || nx >= N || ny >= M || map[nx][ny] == 1)
                    break;
                else {
                    r = nx;
                    c = ny;
                }
            }
        }

        System.out.println(cnt);
    }
}

두번째 코드 - 성공

idx가 시계이고 반시계 방향으로 어떻게 돌리지?

⇒ dx, dy는 시계 방향으로 적음

그리고 d를 -1 하면서 만약 -1이 되면 3으로 바꿈

이유: d가 0인 경우 → 돌려야 하는 방향 (3,2,1,0)

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

public class Main {
    static int[] dx = { -1, 0, 1, 0 }; // 시계방향(북,동,남,서);
    static int[] dy = { 0, 1, 0, -1 };
    static int N, M, r, c, d;
    static int[][] map;

    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());

        st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());

        map = new int[N][M];

        int cnt = 0;

        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());
            }
        }

        while (true) {
            if (map[r][c] == 0) { // 현재 칸 청소
                cnt++;
                map[r][c] = cnt + 1;
            }

            boolean flag = true;

            for (int i = 0; i < 4; i++) {
                d -= 1;
                if (d == -1) {
                    d = 3;
                }

                int nx = r + dx[d];
                int ny = c + dy[d];

                if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                    continue;

                if (map[nx][ny] == 0) {
                    r = nx;
                    c = ny;
                    flag = false;
                    break;
                }
            }

            if (flag) {
                int nx = r + dx[d] * -1;
                int ny = c + dy[d] * -1;

                if (nx < 0 || ny < 0 || nx >= N || ny >= M || map[nx][ny] == 1)
                    break;
                else {
                    r = nx;
                    c = ny;
                }
            }
        }

        System.out.println(cnt);
    }
}