[BOJ] 14503. 로봇 청소기(시뮬레이션, BFS, DFS).java

#. Problem

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

* The copyright in this matter is in BOJ

 

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

시간복잡도는 O(50^2)으로 아주 착한 문제다.

문제에서 주어진 로봇 청소기의 작동법대로 구현해보자.

#. Code_bfs

처음에는 생각 없이 BFS로 해결했는데,

생각해보니까 로봇 청소기는 앞만 보고 달리기 때문에 어떻게 보면 DFS로 해결하는 게 더 적합할 것 같다.

(사실 상관은 없지만..)

문제에서 준 조건대로

1. 현재 위치를 청소하고

2. 현재 방향을 기준으로 왼쪽부터 차례대로 탐색했다.

여기서 아직 청소하지 않은 공간이 존재한다면 그 방향으로 전진하여 1번부터 진행하였고

네 방향 모두 청소가 이미 되어있거나 벽이면 바라보는 방향을 기준으로 후진하고 2번부터 다시 진행하였다.

=> 2번은 계속 재귀적으로 돌아야 하므로 재귀적으로 구현해야 한다.

여기서 뒤쪽이 벽이라 후진도 할 수 없는 상황이 오면 작동을 멈추게 된다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class BOJ14503 {       static int N, M, map[][];     static int[] dr = {-1, 0, 1, 0}, dc = {0, -1, 0, 1}; // 북서남동     static Queue<Robot> q;          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 a = Integer.parseInt(st.nextToken());         int b = Integer.parseInt(st.nextToken());         int c = Integer.parseInt(st.nextToken());         // 북동남서         if(c == 1) c = 3;         else if(c == 3) c = 1;         Robot start = new Robot(a, b, c);                  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());             }         }                  System.out.println(process(start));     }       private static int process(Robot start) {                  int cnt = 0;         q = new LinkedList<>();         q.add(start);                  while(true) {                          Robot now = q.poll();             // 1. 현재 위치를 청소             if(map[now.r][now.c] == 0) {                 // 청소한 곳은 2로 체크                 map[now.r][now.c] = 2;                 cnt++;             }                          // 2. 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색             if(move(now)) continue;             // 작동을 멈출 경우             else return cnt;         }     }       private static boolean move(Robot now) {                  int ndir = 0, rr = 0, cc = 0;         for (int d = 1; d <= 4; d++) {             ndir = (now.dir + d) % 4;             rr = now.r + dr[ndir];             cc = now.c + dc[ndir];             // 이미 청소했거나 벽일 경우             if(map[rr][cc] > 0) continue;               // 아직 청소하지 않은 공간이 존재한다면,              if(map[rr][cc] == 0) {                 // 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행                 q.add(new Robot(rr, cc, ndir));                 return true;             }         }              // 네 방향 모두 청소가 이미 되어있거나 벽인 경우         // 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아감         rr = now.r - dr[now.dir];         cc = now.c - dc[now.dir];         // 하지만, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다         if(map[rr][cc] == 1) return false;         else if(move(new Robot(rr, cc, now.dir))) return true;                  return false;     }       static class Robot {         int r, c, dir;           public Robot(int r, int c, int dir) {             this.r = r;             this.c = c;             this.dir = dir;         }     } } Colored by Color Scripter

cs

#. Code_dfs

DFS로 해결하면 코드가 단순해진다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ14503_v2 {
 
    static int N, M, map[][], cnt;
    static int[] dr = {-1, 0, 1, 0}, 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 Rr = Integer.parseInt(st.nextToken());
        int Rc = Integer.parseInt(st.nextToken());
        int Rd = 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());
            }
        }
        
        process(Rr, Rc, Rd);
        System.out.println(cnt);
    }
 
    private static void process(int r, int c, int dir) {
        
        // 벽일 경우
        if(map[r][c] == 1) return;
        // 1. 현재 위치를 청소
        else if(map[r][c] == 0) {
            // 청소한 곳은 2로 체크
            map[r][c] = 2;
            cnt++;
        }
 
        int rr = 0, cc = 0;
        for (int d = 0; d < 4; d++) {
            dir = (dir + 3) % 4;
            rr = r + dr[dir];
            cc = c + dc[dir];
            // 이미 청소했거나 벽일 경우
            if(map[rr][cc] > 0) continue;
            // 아직 청소하지 않은 공간이 존재한다면, 
            // 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행
            process(rr, cc, dir);
            return;
        }
        
        // 네 방향 모두 청소가 이미 되어있거나 벽인 경우
        // 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아감
        process(r - dr[dir], c - dc[dir], dir);
        return;
    }
 
}

line 41) 벽일 경우는 return, 청소할 수 있는 공간이라면 청소를 한다.

단, 이미 청소를 한 곳일 경우 통과시켜주어야 한다.

이미 청소를 한 곳이더라도 후진해서 왔을 경우도 생각해주어야 한다.

line 50~60) 왼쪽부터 탐색

line 55) 이미 청소했거나 벽일 경우는 pass

line 58) 청소하지 않은 공간이 있다면

line 64) 후진할 경우

뒤쪽이 벽이라 후진도 할 수 없는 상황이 오면 알아서 return .. return 처리가 되어 종료된다.