[BOJ] 3055. 탈출(BFS).java

#. Problem

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

* 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

R과 C의 범위는 최대 50이므로, O(2500)

Naive하게 풀 수 있다.

가장 빠른 이동 시간을 구하기 위해서는?!

BFS가 적합하다.

고슴도치의 이동과 물의 확장은 매분 동시에 이루어진다.

이동과 확장의 동작은 4방으로 동일하게 동작한다.

그러므로 매분 각 Queue(고슴도치, 물)의 Size만큼 동작을 수행해주면 된다.

단, 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다고 했으니까

물을 먼저 확장시킨 후 고슴도치를 이동시켜주면 된다.

전에 코테에서도 비슷한 유형의 문제가 나왔었고

BFS 기본 문제로 좋은 문제인 것 같다 !

#. Code

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 BOJ3055 {       static int R, C;     static int[] dr = {1, 0, -1, 0}, dc = {0, -1, 0, 1};     static char map[][];          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());                  R = Integer.parseInt(st.nextToken());         C = Integer.parseInt(st.nextToken());         map = new char[R][C];         Queue<Point> sQ = new LinkedList<>();         Queue<Point> waterQ = new LinkedList<>();                  for (int i = 0; i < R; i++) {             map[i] = br.readLine().toCharArray();             for (int j = 0; j < C; j++) {                 // 고슴도치의 위치                 if(map[i][j] == 'S') {                     sQ.add(new Point(i, j));                 } else if(map[i][j] == '*') {                     waterQ.add(new Point(i, j));                 }             }         }           int res = process(sQ, waterQ);         // 비버의 굴로 이동할 수 없다면         if(res == 0) System.out.println("KAKTUS");         else System.out.println(res);     }       private static int process(Queue<Point> sQ, Queue<Point> wQ) {           int time = 0, size = 0;                  while(!sQ.isEmpty()) {               ++time;             // 물의 확장             size = wQ.size();             for (int i = 0; i < size; i++) {                 Point water = wQ.poll();                                  for (int d = 0; d < 4; d++) {                     int rr = water.r + dr[d];                     int cc = water.c + dc[d];                     // 범위를 초과하거나 이미 방문                     if(rr < 0 || rr >= R || cc < 0 || cc >= C || map[rr][cc] == '*') continue;                     // 돌이거나 비버의 소굴일 경우                     if(map[rr][cc] == 'X' || map[rr][cc] == 'D') continue;                                          map[rr][cc] = '*';                     wQ.add(new Point(rr, cc));                 }             }                          // 고슴도치의 이동             size = sQ.size();             for (int i = 0; i < size; i++) {                 Point hedgehog = sQ.poll();                                  for (int d = 0; d < 4; d++) {                     int rr = hedgehog.r + dr[d];                     int cc = hedgehog.c + dc[d];                     // 범위를 초과하거나 이미 방문                     if(rr < 0 || rr >= R || cc < 0 || cc >= C || map[rr][cc] == 'S') continue;                     // 돌이거나 물로 차있을 경우                     if(map[rr][cc] == 'X' || map[rr][cc] == '*') continue;                     // 비버의 소굴로 이동할 수 있다면                     if(map[rr][cc] == 'D') return time;                                          map[rr][cc] = 'S';                     sQ.add(new Point(rr, cc));                 }             }         }                  return 0;     }       static class Point {         int r, c;           public Point(int r, int c) {             this.r = r;             this.c = c;         }              } }     Colored by Color Scripter

cs