[백준 5427] - [BFS 최단거리] - 불 (JAVA)

문제링크 : https://www.acmicpc.net/problem/5427

---

이 문제는 BFS를 가지고 풀면 되는데 좌표정보를 갖는 queue를 2개를 사용해야 한다.

queue1은 불의 좌표를 저장하는 queue로 사용하고

queue2는 사람의 좌표를 저장하는 queue로 사용한다.

입력 값이 숫자가 아닌 # * . @ 형식의 char 타입 데이터 이기 떄문에 나는 이 char를 custom 해서 int 형의 값으로 변경했다.

• # --> -1
• * --> -2
• . --> 0
• @ --> 1

방문 정보를 저장할 visited 배열을 사용하기 싫어서 빈 공간은 0으로 두고 사람이 움직일때 좌표의 값이 0인 위치만 이동하게 소스를 작성했다.

복잡하다면 char형의 이차원 배열과 visited 배열을 두개 생성하고 문제를 풀면 된다.

초기 필드는 다음과 같이 사용했다.

public static int ROW;

public static int COL;

public static int[][] building; // 빈공간 . => 0 || 벽 # => -1 || 불 * => 1 || 상근이 @ => 2

public static Queue<int[]> queue1; // 불의 좌표를 저장할 큐

public static Queue<int[]> queue2; // 사람의 좌표를 저장할 큐

public static int result; // 지난 시간을 저장할 큐

public static final String RESULT_FAIL = "IMPOSSIBLE"; 

public static int[] dy = {-1, 1, 0, 0};

public static int[] dx = {0, 0, -1, 1};

그리고 좌표에대한 값을 입력 받을 때의 소스는 다음과 같이 작성했다.

  // 좌표입력

for(int i=0; i < ROW; i++) {

String str = br.readLine();

for(int j=0; j < COL; j++) {

building[i][j] = getVal(str.charAt(j));

if(building[i][j] == -2) queue1.offer(new int[] {i, j});

else if(building[i][j] == 1) queue2.offer(new int[] {i, j, 0});

}

}

불에 대한 좌표를 queue1에 저장했고 사람의 좌표를 저장할때는 y, x 좌표에 0을 저장했는데 0의 값은 지난 시간의 정보라 보면 된다.

모든 값을 입력 받았으면 두 큐가 모두 빈 큐가 될때까지 좌표를 상,하,좌,우 로 이동시키면 된다. 

소스

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

package dfs_bfs.b_5427;   import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.StringTokenizer;   public class Main {       public static int ROW;     public static int COL;          public static int[][] building;        // 빈공간 . => 0 || 벽 # => -1 || 불 * => 1 || 상근이 @ => 2     public static Queue<int[]> queue1;    // 불의 좌표를 저장할 큐     public static Queue<int[]> queue2;    // 사람의 좌표를 저장할 큐     public static int result;            // 지난 시간을 저장할 큐     public static final String RESULT_FAIL = "IMPOSSIBLE";           public static int[] dy = {-1, 1, 0, 0};     public static int[] dx = {0, 0, -1, 1};     public static void main(String[] args) throws IOException{         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = null;                  int testCase = Integer.parseInt(br.readLine());         StringBuilder sb = new StringBuilder();         while(testCase-- > 0) {             st = new StringTokenizer(br.readLine());                          COL = Integer.parseInt(st.nextToken());             ROW = Integer.parseInt(st.nextToken());                          building = new int[ROW][COL];             queue1 = new LinkedList<>();             queue2 = new LinkedList<>();             result = 0;                          // 좌표입력             for(int i=0; i < ROW; i++) {                 String str = br.readLine();                 for(int j=0; j < COL; j++) {                     building[i][j] = getVal(str.charAt(j));                                          if(building[i][j] == -2) queue1.offer(new int[] {i, j});                     else if(building[i][j] == 1) queue2.offer(new int[] {i, j, 0});                 }             }                          bfs();             sb.append((result > 0)?result + "\n":RESULT_FAIL+"\n");         }         System.out.println(sb.toString());     }       public static void bfs() {         while(!queue1.isEmpty() || !queue2.isEmpty()) {                          int size1 = queue1.size();                          if(size1 > 0) {                 while(size1-- > 0) {                     int y = queue1.peek()[0];                     int x = queue1.peek()[1];                     queue1.poll();                                          //불 이동                         for(int i = 0; i< 4; i++) {                         int yy = y + dy[i];                         int xx = x + dx[i];                                                  if(yy < 0 || yy >= ROW) continue;                         if(xx < 0 || xx >= COL) continue;                         if(building[yy][xx] == -1 || building[yy][xx] == -2) continue;    // 벽이거나 이미 불이면 continue                                                  building[yy][xx] = -2;                         queue1.offer(new int[] {yy, xx});                     }                 }             }                                       // 상근이 이동             int size2 = queue2.size();             boolean isEnd = false;             if(size2 > 0) {                 while(size2-- > 0) {                     int y = queue2.peek()[0];                     int x = queue2.peek()[1];                     int t = queue2.peek()[2];                     queue2.poll();                                          for(int i = 0; i < 4; i++) {                         int yy = y + dy[i];                         int xx = x + dx[i];                         if(yy < 0 || yy >= ROW || xx < 0 || xx >= COL) {                             // 탈출 성공!                             result = t+1;                             isEnd = true;                             break;                         }                                                  if(building[yy][xx] == 0) {                             building[yy][xx] = t+1;                             queue2.offer(new int[] {yy, xx, t+1});                         }                     }                     if(isEnd) break;                 }                 if(isEnd) break;             }else {                 result = -1;                 break;             }         }     }       public static int getVal(char c) {         switch(c) {             case '#': return -1;             case '*': return -2;             case '@': return 1;              default: return 0;         }     } }   Colored by Color Scripter

cs