[BOJ] 4179.불(BFS).java

#. Problem

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

* 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

나랑 이름이 같아서

지훈이가 빨리 불 속에서 탈출하길 응원하는 마음으로 문제를 풀었다.

...?

대략적인 동작은

1. 지훈이의 위치와 불의 위치를 저장

2. 불이 먼저 퍼지는데, 범위를 벗어나거나 벽, 이미 방문한 경우는 pass

3. 불이 퍼지고 지훈이가 이동한다. 가장자리(범위를 벗어나면) 지훈이는 탈출을 하게 되고, 

   벽이거나 불이거나 이미 방문한 곳이라면 pass

#. 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

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 BOJ4179_v2 {       static int R, C, res;     static char map[][];     static int[] dx = { -1, 0, 1, 0 }, dy = { 0, 1, 0, -1 };     static Queue<State> fire, jh;     static class State {         int x, y, d;           public State(int x, int y, int d) {             super();             this.x = x;             this.y = y;             this.d = d;         }              }          private static boolean bfs() {                  while(!jh.isEmpty()) {                          // 불이 먼저 퍼진다.             int size = fire.size();             for (int i = 0; i < size; i++) {                 State now = fire.poll();                                  for (int d = 0; d < 4; d++) {                     int xx = now.x + dx[d];                     int yy = now.y + dy[d];                                          // 범위를 벗어나면 pass                     if(xx < 0 || yy < 0 || xx >= R || yy >= C) continue;                     // 벽이거나 방문한 곳이면 pass                     if(map[xx][yy] == '#' || map[xx][yy] == 'F') continue;                                          map[xx][yy] = 'F';                     fire.add(new State(xx, yy, now.d + 1));                 }                 }                              // 지훈이가 불을 피해 이동             size = jh.size();             for (int i = 0; i < size; i++) {                 State now = jh.poll();                                  for (int d = 0; d < 4; d++) {                     int xx = now.x + dx[d];                     int yy = now.y + dy[d];                                          // 지훈이는 범위를 벗어나면 탈출                     if(xx < 0 || yy < 0 || xx >= R || yy >= C) {                         res = now.d + 1;                         return true;                     }                                          // 벽이거나 불이거나 방문한 곳이면 pass                     if(map[xx][yy] == '#' || map[xx][yy] == 'F' || map[xx][yy] == 'J') continue;                                          map[xx][yy] = 'J';                     jh.add(new State(xx, yy, now.d + 1));                 }                 }         }           return false;     }          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];                  fire = new LinkedList<>();         jh = 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] == 'J') {                     jh.add(new State(i, j, 0));                 }                 // 불의 위치                 else if(map[i][j] == 'F') {                     fire.add(new State(i, j, 0));                 }             }         }                  if(bfs()) System.out.println(res);         else System.out.println("IMPOSSIBLE");     } }   Colored by Color Scripter

cs