[백준] 14503 로봇 청소기

문제

1. 현재 칸 청소하기

2. 현재칸 주변 4칸 청소되지 않은칸이 존재하면 않으면 -> 후진 -> 1번 되돌아가기

3. 현재칸 주변 4칸 청소되지 않은칸이 존재하면 -> 반시계 방향 90도 회전 -> 청소안된칸이면 전진 -> 1번으로 돌아가기

 

---

풀이방법

- 풀이 시간 : 10분

- 접근 방식 : DFS

 

단순하게 DFS를 사용해 문제를 풀이하면 된다.

 

2,3번을 반대로 생각하면 편하다. 그냥 우선순위를 반시계방향 90도라고 생각하고 반시계방향 90도를 하나씩 살펴본다. 만약 4군데 다 청소가 되었다면 후진하는 로직으로 들어가면 된다.

 

만약 하나라도 청소가 안된 칸을 발견하면 들어가고 return 해주면 된다.

---

코드

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

public class 로봇청소기 {
    static int N, M;
    static int[][] map;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    static int result;
    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());

        st = new StringTokenizer(br.readLine());
        map = new int[N][M];

        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        int dir = 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());
            }
        }
        result = 0;
        dfs(x, y, dir);

        System.out.println(result);
    }

    private static void dfs(int cx, int cy, int dir){
        if(map[cx][cy] == 0){
            map[cx][cy] = 2;
            result++;
        }
        for(int i = 0; i < 4; i++){
            dir = (dir + 3) % 4;
            int nx = cx + dx[dir];
            int ny = cy + dy[dir];

            if(0 <= nx && nx < N && 0 <= ny && ny < M && map[nx][ny] == 0){
                dfs(nx, ny, dir);
                return;
            }
        }

        int fakeDir = (dir + 2) % 4;
        int nx = cx + dx[fakeDir];
        int ny = cy + dy[fakeDir];
        if(0 <= nx && nx < N && 0 <= ny && ny < M && map[nx][ny] != 1){
            dfs(nx, ny, dir);
        }  
    }
}