[BOJ] 3197. 백조의 호수(BFS).java

#. Problem

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

* 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

문제를 풀면서 백조의 호수 BMG이 들리는 감수성 있는 문제..

[BOJ] 2573. 빙산(DFS, BFS).java

[BOJ] 2636.치즈(BFS, DFS).java

의 상위(?) 문제 같다.

N 의 범위가 1 ≤ N ≤ 1500 라서

O(N^2) 안에 수월하게(?) 해결할 수 있을 것 같지만

잘못 생각하면 O(N^3)이 되어 TLE 이 발생할 수 있다.

두 백조가 만날 수 있는지 확인(O(N^2))할 때와

빙하를 녹일 때(O(N^2))를 한 번만 수행해주어야 O(N^2)만에 해결할 수 있다.

매 시간마다,

모든 구간을 탐색하며 두 백조가 만날 수 있는지 확인하고

모든 구간을 탐색하며 빙하를 녹인다면

TLE이 발생할 수 있다.

//

두 백조가 만날 수 있는지 확인할 때는 O(N^2) 안에 수행하기 위해

탐색 중 빙하로 막혀 있다면 다음 날 탐색할 수 있도록 큐에 저장해두고

다음 날 큐에 저장해둔 위치부터 탐색하면 된다.

빙하도 마찬가지로 O(N^2) 안에 수행하기 위해

다음 날 탐색할 위치를 큐에 저장해두면 된다.

#. 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 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134

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 BOJ3197 {       static int R, C, idx, cur = 0, nxt = 1;     static char map[][];     static boolean[][] vstdIn, vstdOut;     static int[] dr = {-1, 0, 1, 0}, dc = {0, -1, 0, 1};     static Queue<Point>[] water, swan;     static Point swans[];          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];         swans = new Point[2]; // 두 백조의 위치 정보         // 물과 빙판 위치를 저장하는 Queue         water = new LinkedList[2];         water[0] = new LinkedList<>();         water[1] = new LinkedList<>();         // 백조가 현재와 다음 날 탐색할 위치를 저장하는 Queue          swan = new LinkedList[2];         swan[0] = new LinkedList<>();         swan[1] = 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] == 'L') {                     swans[idx++] = new Point(i, j);                     map[i][j] = '.';                 }                  // 물의 위치를 저장                 if(map[i][j] == '.') {                     water[cur].add(new Point(i, j));                 }             }         }                  System.out.println(process());     }       private static int process() {                  int time = 0;         vstdIn = new boolean[R][C];         vstdOut = new boolean[R][C];         // 0번 백조가 1번 백조를 향해         swan[cur].add(swans[0]);         vstdIn[swans[0].r][swans[0].c] = true;                  while(true) {             // 두 마리의 백조가 만날 수 있는지 확인             if(isMeet()) return time;             // 빙하가 녹는다             melt();             // index switch             cur ^= 1;             nxt ^= 1;                          time++;         }     }       private static boolean isMeet() {         // 현재 백조가 갈 수 있는 구간을 모두 탐색         while(!swan[cur].isEmpty()) {             Point now = swan[cur].poll();                          // 4방 탐색             for (int d = 0; d < 4; d++) {                 int rr = now.r + dr[d];                 int cc = now.c + dc[d];                 // 범위를 초과하거나 이미 방문했을 경우 pass                 if(rr < 0 || cc < 0 || rr >= R || cc >= C || vstdIn[rr][cc]) continue;                 // 상대 백조를 만났을 경우 return                 if(rr == swans[1].r && cc == swans[1].c) return true;                 // 방문 처리                 vstdIn[rr][cc] = true;                 // 빙하일 경우 다음 날 탐색을 위해 Queue에 추가                 if(map[rr][cc] == 'X') {                     swan[nxt].add(new Point(rr, cc));                     map[rr][cc] = '.';                 } else {                     swan[cur].add(new Point(rr, cc));                 }             }         }                  return false;     }       private static void melt() {         // 물이 있는 구간을 모두 탐색         while(!water[cur].isEmpty()) {             Point now = water[cur].poll();                          // 4방 탐색             for (int d = 0; d < 4; d++) {                 int rr = now.r + dr[d];                 int cc = now.c + dc[d];                 // 범위를 초과하거나 이미 방문했을 경우                 if(rr < 0 || cc < 0 || rr >= R || cc >= C || vstdIn[rr][cc] || vstdOut[rr][cc]) continue;                 vstdOut[rr][cc] = true;                 // 빙산일 경우                 if(map[rr][cc] == 'X') {                     // 물 공간과 접촉한 모든 빙판 공간이 녹는다.                     map[rr][cc] = '.';                     water[nxt].add(new Point(rr, cc));                 }              }         }     }       static class Point {         int r, c;                  public Point(int r, int c) {             this.r = r;             this.c = c;         }     }      } Colored by Color Scripter

cs