[Java] 백준(골드-4) 4179번 - 불!
문제 풀이
이번 문제는 너비 우선 탐색인 BFS를 잘 숙지하고 있고, 이를 응용할 수 있어야 풀 수 있다.
아이디어 도출
지훈이가 불이 번지는 것을 피해 탈출하기 까지의 최소 시간(이동횟수)를 구해야 한다. 여기서 문제의 핵심은 BFS 탐색 안에서 불이 번지는 것과 지훈이가 불을 피해 이동하는 2가지 과정을 수행해야 한다.
문제 해결을 위해 생각한 아이디어는 다음과 같다.
- 지훈이와 불의 위치를 담을 방문배열과 큐를 각각 2개씩 활용한다.
- 이때, 방문배열은 boolean형 타입이 아니라 int형 타입의 배열로 선언하여 지훈이와 불의 이동시간을 기록한다.
- 미로 배열을 입력받으면, 지훈이의 위치를 지훈이 위치를 처리할 큐에 담고, 불의 위치를 불의 위치를 처리할 큐에 담는다.
- BFS 함수 안에서 다음을 수행한다.
- 4.1 먼저 불이 번지는 탐색을 진행하여, 지훈이가 이동하지 못할 위치에 불을 번지게 한다.
- 4.2 불이 번진 후, 지훈이가 이동할 수 있는 위치로 이동한다.
- 4.3 지훈이가 미로의 가장자리를 벗어나면 여태 이동한 시간(횟수)을 출력한다.
이때, 지훈이가 이동할 곳을 탐색할 때 불이 먼저 번져있다면 이동할 수 없음을 주의해야 한다.
위와 같이 불이 담긴 큐와 지훈이가 담긴 큐에서 각각 상,하,좌,우 탐색을 진행하면서 불이 번질 곳을 먼저 갱신한 후, 지훈이가 이동할 수 있는 위치로 이동을 시키면 된다. 그렇게 이동을 해가면서 지훈이가 미로의 가장자리를 벗어나면 탈출이 성공한 것이기에 지훈이가 이동한 횟수(시간)을 출력하면 되며, 지훈이가 미로 안에서 상,하,좌,우로 이동할 수 없이 고립되었다면 탈출하지 못하는 것이기에 "IMPOSSIBLE"을 출력한다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
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
135
136
137
import java.io.*;
import java.util.*;
class Main {
// 입력 N, M 선언
static int N;
static int M;
// 상하좌우를 탐색하기 위한 dx, dy 배열 선언
static int[] dx = new int[]{0, 1, 0, -1};
static int[] dy = new int[]{1, 0, -1, 0};
// 불과 지훈이의 이동 여부를 담을 방문 배열 선언
static int[][] visited_jihun;
static int[][] visited_fire;
// 불과 지훈이의 위치를 담을 큐 선언
static Queue<int[]> jq = new LinkedList<>();
static Queue<int[]> fq = new LinkedList<>();
// 미로 배열 선언
static String[][] miro;
// 탈출 여부를 판단할 boolen 변수
static boolean escape;
// 탈출 시 지훈이의 이동 시간을 출력할 변수
static int result;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// 미로배열 초기화
miro = new String[N][M];
// 방문 배열 초기화
visited_jihun = new int[N][M];
visited_fire = new int[N][M];
// 불과 지훈이의 위치를 각각 fq, jq에 담는다.
// 또한 지훈이와 불이 이동 시간을 저장하기 위해 불, 지훈, '.' 위치마다 방문 배열을 갱신한다.
for(int i=0; i<N; i++) {
String[] input = br.readLine().split("");
for(int j=0; j<M; j++) {
miro[i][j] = input[j];
if(miro[i][j].equals("F")) {
visited_fire[i][j] = 1;
fq.offer(new int[]{i, j});
} else if(miro[i][j].equals("J")) {
visited_jihun[i][j] = 1;
jq.offer(new int[]{i, j});
} else if(miro[i][j].equals(".")) {
visited_fire[i][j] = -1;
visited_jihun[i][j] = -1;
}
}
}
escape = false;
result = 0;
BFS();
if(escape) {
bw.write(result+"\n");
} else {
bw.write("IMPOSSIBLE"+"\n");
}
bw.close();
br.close();
}
static void BFS() {
// 1. 불이 먼저 퍼진다.
while(!fq.isEmpty()) {
int[] now = fq.poll();
for(int dir=0; dir<4; dir++) {
int i = now[0] + dx[dir];
int j = now[1] + dy[dir];
if(isRange(i, j)) {
// 벽이거나 이미 불이 번진 위치인 경우
if(visited_fire[i][j] >= 1 || miro[i][j].equals("#")) {
continue;
}
// 불이 번질 수 있는 위치라면 불이 번진다.
visited_fire[i][j] = visited_fire[now[0]][now[1]] + 1;
fq.add(new int[]{i, j});
}
}
}
// 2. 불이 퍼진 후 지훈이가 이동한다.
while(!jq.isEmpty()) {
int[] now = jq.poll();
for(int dir=0; dir<4; dir++) {
int i = now[0] + dx[dir];
int j = now[1] + dy[dir];
// 지훈이가 미로의 범위를 벗어난다면 탈출
if(!isRange(i, j)) {
escape = true;
result = visited_jihun[now[0]][now[1]];
return;
}
if(isRange(i, j)) {
// 지훈이가 움직일 수 없는 위치일 경우
if(visited_jihun[i][j] >= 1 || miro[i][j].equals("#")) {
continue;
}
// 이미 불이 전파되어 움직일 수 없는 경우
// 지훈이가 이동할 시간이 더 크다면 불은 그 전 시간에 전파되었기 때문
if(visited_fire[i][j] != -1 && (visited_fire[i][j] <= visited_jihun[now[0]][now[1]]+1)) {
continue;
}
// 지훈이가 이동할 수 있는 위치로 이동한다.
visited_jihun[i][j] = visited_jihun[now[0]][now[1]] + 1;
jq.add(new int[]{i, j});
}
}
}
}
// 좌표의 범위가 배열을 벗어났는지 확인할 함수
static boolean isRange(int x, int y) {
if(0<=x && 0<=y && x<N && y<M) {
return true;
}
return false;
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.