알고리즘/BFS_DFS

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

팡스 2018. 12. 20. 13:57

문제링크 : 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;
        }
    }
}
 
cs



저작자표시