알고리즘/탐색

[백준] 14503 로봇 청소기 (DFS) - Java

jny0 2023. 5. 17. 16:07

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

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

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

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

 

입력

첫째 줄에 방의 크기 과 이 입력된다.   둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 와 처음에 로봇 청소기가 바라보는 방향 가 입력된다. 가 0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽을 바라보고 있는 것이다.

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

 

출력

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

 

 

접근법

  1. 현재 위치가 청소되지 않았다면 청소
  2. 현재 방향에서 반시계 방향으로 탐색
    • 청소할 수 있는 공간이면 전진 → 1번
  3. 벽을 만나거나 청소할 수 있는 공간이 없는 경우
    • 방향을 유지한 채 후진 → 1번
    • 뒤쪽에 벽이 있을 경우 후진 불가 → 종료

 

 

문제 풀이

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

public class Main {
    static int N, M;
    static int count;
    static int[][] room;
    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 InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        room = new int[N][M];

        st = new StringTokenizer(br.readLine());

        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        count = 1;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                room[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(r, c, d);

        System.out.println(count);
    }

    static void dfs(int r, int c, int d) {
        room[r][c] = -1; // 현재 위치 청소

        // 반시계 방향으로 탐색
        for (int i = 0; i < 4; i++) {
            d = (d + 3) % 4; //
            int nx = r + dx[d];
            int ny = c + dy[d];

            // 범위 안에 있고 청소가 안된 구역이라면 count++, dfs 재귀
            if (ny >= 0 && ny < M && nx >= 0 && nx < N && room[nx][ny] == 0){
                count++;
                dfs(nx, ny, d);
                return;
            }
        }

        int back = (d + 2) % 4;
        int bx = r + dx[back];
        int by = c + dy[back];

        // 주변에 청소할 구역이 없으면 방향은 유지하면서 후진, dfs 재귀
        // 뒤쪽이 벽이면 후진 불가 -> 종료
        if (by >= 0 && by < M && bx >= 0 && bx < N && room[bx][by] != 1) {
            dfs(bx, by, d);
        }
        
    }
}
저작자표시 (새창열림)