[baekjoon] 로봇 청소기 JAVA

 

https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

 

* 코딩테스트에서 가장 중요한 점은 문제를 잘 이해하는 것이다.

- 로봇 청소기 문제에서는 청소기가 왼쪽으로 돌며 청소한다는 점과 4가지 방향을 다 돌고 난 후

  후진을 할 경우는 왼쪽으로 2번 돌려 이동한 것과 마찬가지이지만 방향은 그대로 인 것을 기억해야한다.

 

* 그리고 나머지 부분은 dfs 로 풀어주면 된다.

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) {
            	//청소X
                if(board[nx][ny] == 0) { 
                    count++;
                    dfs(nx, ny, dir);
                    return;
                }
            }
        }
        
        //반목문을 빠져 나왔다는 것은 4가지 방향으로 다 돌았음
        //즉 청소 할 곳이 없다는 것
        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); //후진할 때 방향을 유지해야 한다.
        }
    }
}