[백준 14503] 로봇 청소기

 

문제에 나와있는 규칙을 잘 지키며 BFS를 수행해야 한다.

주의할 점은 따로 없어 코드에 주석을 달아놓았다.

 

 

public class Main {
    
    static int n;
    static int m;
    static int a[][];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        m = sc.nextInt();
        a = new int[n][m];
        
        int r = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                a[i][j] = sc.nextInt();
        
        System.out.println(bfs(r, c, d));
    }
    
    //(r, c):좌표, d:방향(0-북, 1-동, 2-남, 3-서)
    public static int bfs(int r, int c, int d) {
        Queue<Pair> q = new LinkedList<Pair>();
        boolean visited[][] = new boolean[n][m];
        
        int dn[] = {0, -1, 0, 1};
        int dm[] = {-1, 0, 1, 0};
        
        q.offer(new Pair(r, c, d));
        visited[r][c] = true; //true이면 청소 완료
        
        while(!q.isEmpty()) {
            Pair p = q.poll();
            int pr = p.r;
            int pc = p.c;
            int pd = p.d;
            
            boolean clean = false;
            for(int i=0; i<4; i++) {
                int nr = pr + dn[pd];
                int nc = pc + dm[pd];
                int nd = pd - 1;
                nd = nd < 0 ? 3 : nd; //0, 1, 2, 3 값 유지
                if(0 <= nr && nr < n && 0 <= nc && nc < m) {
                    if(a[nr][nc] == 0 && !visited[nr][nc]) {
                        visited[nr][nc] = true;
                        q.offer(new Pair(nr, nc, nd));
                        clean = true;
                        break;
                        //청소를 성공하면 BFS탐색을 새로 시작함
                    } else {
                        pd--;
                        pd = pd < 0 ? 3 : pd;
                    }
                }
            }
            //청소를 한군데도 못했다면
            if(!clean) {
                int br[] = {1, 0, -1, 0};
                int bc[] = {0, -1, 0, 1};
                //후진 정보를 담은 배열
                int nr = pr + br[pd];
                int nc = pc + bc[pd];
                if(0 <= nr && nr < n && 0 <= nc && nc < m) {
                    if(a[nr][nc] != 1)
                        q.offer(new Pair(nr, nc, pd));
                } else break;
                //후진할 곳이 없으면 탐색을 멈춤
            }
        }
        
        int cnt = 0;
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                if(visited[i][j])
                    cnt++;
        return cnt;
    }
    
    static class Pair {
        int r;
        int c;
        int d;
        
        Pair(int r, int c, int d) {
            this.r = r;
            this.c = c;
            this.d = d;
        }
    }
}