[백준] 14503 로봇 청소기 (JAVA)

풀이

이 문제는 처음에 보았을떄는 난해하였으나 천천히 보면 크게 두가지로 볼수있다. 해당 위치에서 상하좌우로 탐색하는 경우와 탐색할 수있는곳이 없는 두가지가 있다. 첫번째는 재귀를 이용한 DFS처럼 하여 탐색을 한다, 이때 만약 탐색이 가능하다면 따로 boolean 변수를 이용해 확인을 한다. 이때 역시 재귀를 이용한 DFS를 이용해서 탐색한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {
    public static int N, M;
    public static int[][] map;
    public static int cnt = 0;
    public static int[] dr = {-1, 0, 1, 0};
    public static int[] dc = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];

        st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        clean(r, c, d);
        br.close();
        System.out.println(cnt);

    }

    public static void clean(int row, int col, int direction) {
        if (map[row][col] == 0) {
            map[row][col] = 2;
            cnt++;
        }

        int origin = direction;
        boolean flag = false;
        for (int i = 0; i < 4; i++) {
            int next_dir = (direction + 3) % 4;
            int next_r = row + dr[next_dir];
            int next_c = col + dc[next_dir];
            if (0 < next_r && next_r < N && 0 < next_c && next_c < M) {
                if (map[next_r][next_c] == 0) {
                    clean(next_r, next_c, next_dir);
                    flag = true;
                    break;
                }
            }
            direction = (direction + 3) % 4;
        }

        if(!flag){
            int next_d = (origin+2)%4;
            int next_br = row + dr[next_d];
            int next_bc = col + dc[next_d];

            if(0< next_br && next_br < N && 0 < next_bc && next_bc < M){
                if(map[next_br][next_bc] != 1){
                    clean(next_br, next_bc, origin);
                }
            }
        }
    }
}