[BOJ] 백준 [14503] 로봇 청소기 JAVA

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

14503번: 로봇 청소기

문제

풀이

단순 DFS 시뮬레이션 문제이다. 특이한점은 dfs 안의 다른 조건으로 재귀호출을 두 번 한다는것.

map[y][x] = 1 : 벽

map[y][x] = 2 : 청소 된 상태로 만들기

map[y][x] = 0 : 청소 안된 상태

문제에 나와있는 조건을 따라서 탐색한 방향 nextX,nextY 가 청소되어있는지 확인 후 움직이거나

청소가 다 되어 있거나 벽인경우 , 후진 할 수 있다면 후진하게 만들면 된다.

import java.util.*;
import java.io.*;
 
public class Main{
 
    static int[][] map;
    static int w,h;
    static int cnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        h = Integer.parseInt(input[0]); w = Integer.parseInt(input[1]);
        input = br.readLine().split(" ");
        int y = Integer.parseInt(input[0]);
        int x = Integer.parseInt(input[1]);
        int dir = Integer.parseInt(input[2]);
        map = new int[h][w];
        for(int i=0;i<h;i++){
            input = br.readLine().split(" ");
            for(int j=0;j<w;j++)
                map[i][j] = Integer.parseInt(input[j]);
        }
        cnt = 0;
        dfs(x,y,dir);
        System.out.println(cnt);
    }
 
    static void dfs(int x, int y, int dir) {
        clean(x,y);
        int rotatedDir = dir;
        for(int i=0;i<4;i++){
            rotatedDir = rotate(rotatedDir);
            int nextX=x,nextY=y;
            switch (rotatedDir) {
                case 0 : nextY--;
                    break;
                case 1 : nextX++;
                    break;
                case 2 : nextY++;
                    break;
                case 3 : nextX--;
                    break;
            }
            if(!isRange(nextX,nextY) || map[nextY][nextX]==1 || map[nextY][nextX]==2)
                continue;
            if(map[nextY][nextX] == 0) {
                dfs(nextX, nextY, rotatedDir);
                return;
            }
        }
        int nextX=x,nextY=y;
        switch (rotatedDir) {
            case 0 : nextY++;
            break;
            case 1 : nextX--;
            break;
            case 2 : nextY--;
            break;
            case 3 : nextX++;
            break;
        }
        if(isRange(nextX,nextY) && map[nextY][nextX] != 1)
            dfs(nextX,nextY,dir);
    }
 
    static boolean isRange(int x,int y){
        return x>=0&&y>=0&&x<w&&y<h;
    }
    static void clean(int x,int y){
        if(map[y][x] == 0){
            cnt++;
            map[y][x] = 2;
        }
    }
    static int rotate(int dir){
        if(dir==0)
            return 3;
        return dir-1;
    }
}