[백준]14503: 로봇 청소기 - JAVA

[백준]14503: 로봇 청소기 - JAVA

www.acmicpc.net/problem/14503

14503번: 로봇 청소기

풀이

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

 

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

예를들어서 아래와 같은 경우이고 시작 위치가 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이므로 작동을 멈춰야 한다.

 

코드

import java.util.*;
 
public class Main {    
    
    static int n, m, r, c, d;
    static int[][] board;
    static int count = 1; //시작 지점은 항상 청소한다.
    static int[] dx = {-1, 0, 1, 0}; //북, 동, 남, 서 순서대로
    static int[] dy = {0, 1, 0, -1};
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        m = scan.nextInt();
        r = scan.nextInt();
        c = scan.nextInt();
        d = scan.nextInt();
        
        board = new int[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                board[i][j] = scan.nextInt();
            }
        }
        
        dfs(r, c, d);
        System.out.println(count);
    }    
    
    public static void dfs(int x, int y, int dir) {
        board[x][y] = 2; //청소 했다는 의미
        
        for(int i = 0; i < 4; i++) {
            dir -= 1; //왼쪽 방향으로 돌면서 탐색
            if(dir == -1) dir = 3;
            
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if(nx >= 0 && ny >= 0 && nx < n && ny < m) {
                if(board[nx][ny] == 0) { //벽도 아니고 이미 청소한 곳도 아니라면 청소하러 이동한다
                    count++;
                    dfs(nx, ny, dir);
                    //일반적인 dfs는 가다가 길이 막히면 다시 되돌아와서 해당 위치부터 계산하지만, 이 문제는 후진할 때만 이전 길을 되돌가 가며 확인할 수 있으므로 return을 해서 다시 되돌아 와도 더 이상 움직이면 안된다.
                    return;
                }
            }
        }
        
        //반목문을 빠져 나왔단는 것은 주변에 더 이상 청소할 공간이 없다는 의미이다.
        int d = (dir + 2) % 4; //반대 방향으로 후진하기 위함.
        int bx = x + dx[d];//후진
        int by = y + dy[d];//후진
        if(bx >= 0 && by >= 0 && bx < n && by < m && board[bx][by] != 1) {
            dfs(bx, by, dir); //후진할 때 방향을 유지해야 한다.
        }
    }
}