[BOJ] 백준 14503 : 로봇 청소기 (java)

🧪 14503 로봇 청소기

---

난이도 : 🌟 골드 5
유형 : 그래프 탐색

14503번: 로봇 청소기

 

📝 문제

---

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

로봇 청소기가 있는 방은 N * M 크기의 직사각형으로 나타낼 수 있으며, 1 * 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도 회전한다.

    2. 바라보는 방향을 기준을 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.

    3. 1번으로 돌아간다.

 

입력

 

첫째 줄에 방의 크기 N과 M이 입력된다. (3 <= N, M <= 50) 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 (r, c)와 처음에 로봇 청소기가 바라보는 방향 d가 입력된다. d가 0일 때 북, 1일때 동, 2일때 남, 3일때 서이다.

셋째 줄부터 N개의 줄에 각 장소의 상태를 나타내는 N * M개의 값이 한 줄에 M개씩 입력된다. i번째 줄의 j번째 값은 칸 (i, j)의 상태를 나타내며, 이 값이 0인 경우 (i, j)가 청소되지 않은 빈 칸이고, 1인 경우 (i, j)에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

 

출력

 

로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

 

🧐 핵심 로직

---

조건에 맞는 모든 경우를 탐색해야 하므로 dfs를 사용한다.

여기서 중요한 조건은 탐색을 할 때에는 이전으로 되돌아 갈 수 없다는 조건이다.

ex) 아래와 같은 경우이고 시작 위치가 (1, 1) 일때

1	0	0
1	0	1
1	0	0

dfs로 탐색을 한 방향으로 하고 난 후

1	2	2
1	2	1
1	0	0

이후에는 원래 dfs라면 (1, 1) 로 돌아와 탐색을 안한 부분을 탐색해 줄 것이다.

그러나 이 문제에서는 탐색 중에서는 되돌아와서 다시 탐색을 진행할 수 없고, 더 이상 갈 수 없어 후진할 때만 이전의 노드를 재 방문할 수 있다.

1	2	2
1	2	1
1	0	0

그러므로 현재 노드가 (0, 2) 일때 더 이상 갈 수 있는 방향이 없으므로 후진을 한다. 이전 노드로 이동한다.

1	2	2
1	2	1
1	0	0

후진한 노드인 (0, 1) 일때 4방향 모두 청소가 되어있고 후진할 수 있는 방향은 1이므로 작동을 멈춘다.

 

💻 최종 코드 (132 ms)

---

 

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

public class Main {

    static int n, m, cnt;
    static int r, c, d;
    static int[][] board;
    static int[] dx = {-1, 0, 1, 0}; 
    static int[] dy = {0, 1, 0, -1};
    public static void main(String[] args) throws IOException {

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        cnt = 1;
        board = 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++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(r, c, d);

        System.out.println(cnt);
    }

    public static void dfs(int x, int y, int d) {

        board[x][y] = 2;

        for (int i=0; i<4; i++) {

            d -= 1; 
            if (d == -1) d = 3;

            int nx = x + dx[d]; 
            int ny = y + dy[d];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] == 0) {

                cnt++;
                dfs(nx, ny, d);
                return;
            }
        }

        int b = (d + 2) % 4; //반대 방향으로 후진.
        int bx = x + dx[b]; //후진
        int by = y + dy[b];
        if (bx >= 0 && bx < n && by >= 0 && by < m && board[bx][by] != 1) {
            dfs(bx, by, d); 
        }
    } 
}

 

cf ) https://moonsbeen.tistory.com/12