[Java] 백준 14503 : 로봇 청소기

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

14503번: 로봇 청소기

---

N*M의 칸을 청소하는 로봇청소기가 있는데, 1은 벽 0은 방이다. 

이때 로봇청소기가 청소할 수 있는 방의 개수를 구하는 문제이다. 

 

조건 

1. 처음 빈칸은 청소되어 있지 않다. 

2. 현재 칸의 주변 4칸 중 청소되지 않은 빈칸이 없는 경우 후진가능하면 후진하고 불가능하면 종료한다.

3. 현재 칸의 주변 4칸 중 청소되지 않은 빈칸이 있는 경우 반시계로 90도 회전하여 전진

4. 처음 바라보는 방향이 0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽을 바라보고 있다. 

 

 

구현 

1. arr [x][y]==0 이면 cnt++ 하고 arr [x][y]=-1 해준다. 

2. 새롭게 이동한 위치가 범위 내에 있는지 확인하고 arr [x][y]==0이라면 clean() 함수를 재귀한다. 

 for(int i = 0; i < 4; i++) {
        	dir = (dir+3)%4;
                       
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if(nx >= 0 && ny >= 0 && nx < N && ny < M) {
                if(arr[nx][ny] == 0) {
                    count++;
                    clean(nx, ny, dir);
                    return;
                }
            }
        }

3. 주변 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 && arr[bx][by] != 1) {
        	clean(bx, by, dir); //후진이니까 바라보는 방향은 유지
        }

 

 

---

전체

import java.util.*;

public class Main {    
    
    static int N, M, r, c, d;
    static int[][] arr;
    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();
        
        arr = new int[N][M];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
            	arr[i][j] = scan.nextInt();
            }
        }
        
        clean(r, c, d);
        System.out.println(count);
    }    
    
    public static void clean(int x, int y, int dir) {
    	
    	arr[x][y] = -1; 
        
        for(int i = 0; i < 4; i++) {
        	dir = (dir+3)%4;
                       
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if(nx >= 0 && ny >= 0 && nx < N && ny < M) {
                if(arr[nx][ny] == 0) {
                    count++;
                    clean(nx, ny, dir);
                    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 && arr[bx][by] != 1) {
        	clean(bx, by, dir); //후진이니까 바라보는 방향은 유지
        }
    }
}
// class Main