반응형
1. 언어 : JAVA
2. 난이도 : Gold 4
3. 풀이
이 문제 역시 BFS이다.
아니 왜 그냥 골드4짜리에서 무작위로 고르는데 자꾸 BFS 문제가 나오는거지?
Anyway
이 문제는 BFS를 1개를 돌리면 되는 문제가 아니란걸 직감으로 느꼈다.
(사실 예전에 이런 비슷한 유형을 풀어본것 같기도?)
BFS문제는 설명하기가 힘든것 같다..
변수는 다음과 같다.
2차원 배열 check
2차원 배열 map
dequeSang // 상근이 큐
dequeFire // 불 큐
check는 상근이가 과거에 진입한 공간인지 아닌지 체크하는 곳
map은 벽과 불이 체크되어있는 곳.
BFS가 진행되면
1. Fire가 주위로 번지고(map에 표시)
2. 상근이가 있던곳 상하좌우 움직인다.
3-1. 만약 상근이가 움직이려고 하는 곳에 벽이나 Fire가 있으면 다음 단계 진행x
3-2. 만약 상근이가 움직이려고 하는 곳에 아무 장애물도 없으면 다음 단계 진행.
이렇게 하다보면 ,상근이가 벽쪽에 위치해 있을 때, 시간을 출력해주면된다.
설명보단 소스코드를 보면서 이해하는게 빠를 것같다.
혼자하면 이게문제야, 다른 코드도 보고싶은데 못봄.. 내가짠건 스파게티코드인데 흑흑 ㅜㅜ
4. 소스코드
import java.io.*;
import java.util.*;
class P {
int y;
int x;
public P(int y, int x) {
this.x = x;
this.y = y;
}
}
public class Main {
public static int [] dx = {0, 0, -1, 1};
public static int [] dy = {-1, 1, 0, 0};
public static void main(String [] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
String [][] map = null;
int [][] check= null;
Deque <P> dequeSang = null;
Deque <P> dequeFire = null;
int w = 0;
int h = 0;
for(int t=0; t<T; t++) {
String [] temp = br.readLine().split(" ");
w = Integer.parseInt(temp[0]);
h = Integer.parseInt(temp[1]);
map = new String[h][w];
check = new int[h][w];
dequeSang = new ArrayDeque<>();
dequeFire = new ArrayDeque<>();
int fireNum = 0;
int sangNum = 0;
for(int i=0; i<h; i++) {
String s = br.readLine();
for(int j=0; j<w; j++) {
String st = s.substring(j, j+1);
if(st.equals("@")) {
check[i][j] = 1;
sangNum ++;
map[i][j] = ".";
bw.flush();
dequeSang.addLast(new P(i, j));
}
else if(st.equals("*")) {
fireNum ++;
dequeFire.addLast(new P(i, j));
map[i][j] = st;
}
else {
map[i][j] = st;
}
}
}
int fireNumTemp = 0;
int sangNumTemp = 0;
boolean find = false;
int result = 0;
int time = 0;
while(!dequeFire.isEmpty() || !dequeSang.isEmpty()) {
if(find) {
break;
}
time ++;
// fire Spread
for(int i=0; i<fireNum; i++) {
P pfire = dequeFire.pollFirst();
int py = pfire.y;
int px = pfire.x;
for(int j=0; j<4; j++) {
int ny = py + dy[j];
int nx = px + dx[j];
if(ny <= -1 || nx <= -1 || ny >= h || nx >= w) {
continue;
}
if(map[ny][nx].equals("#") || map[ny][nx].equals("*")) {
continue;
}
fireNumTemp ++;
map[ny][nx] = "*";
dequeFire.add(new P(ny, nx));
}
}
fireNum = fireNumTemp;
fireNumTemp = 0;
for(int i=0; i<sangNum; i++) {
P psang = dequeSang.pollFirst();
int py = psang.y;
int px = psang.x;
for(int j=0; j<4; j++) {
int ny = py + dy[j];
int nx = px + dx[j];
if(ny <= -1 || nx <= -1 || ny >= h || nx >= w) {
find = true;
result = time;
continue;
}
if(map[ny][nx].equals("*") || map[ny][nx].equals("#") || check[ny][nx] != 0) {
continue;
}
sangNumTemp ++;
check[ny][nx] = 1;
dequeSang.addLast(new P(ny, nx));
}
}
sangNum = sangNumTemp;
sangNumTemp = 0;
}
if(result == 0)
bw.write("IMPOSSIBLE\n");
else
bw.write(result + "\n");
bw.flush();
}
}
}
반응형
'Algorithm > BFS' 카테고리의 다른 글
| BOJ No.1261[알고스팟] (0) | 2021.03.12 |
|---|---|
| BOJ No.12886[돌덩이] (0) | 2021.03.11 |
| BOJ No.1005[AC Craft] (0) | 2021.03.11 |
