이번에 풀어본 문제는
백준 4179번 불! 입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Location {
int x, y;
int time;
public Location(int x, int y, int time) {
this.x = x;
this.y = y;
this.time = time;
}
}
public class Main {
static int R,C;
static char [][] map;
static int [][] burnedTime;
static boolean [][] isVisited;
static int [] dx = {-1, 1, 0, 0};
static int [] dy = {0, 0, -1, 1};
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];
isVisited = new boolean[R][C];
burnedTime = new int[R][C];
Queue<Location> q = new LinkedList<>();
//초기화
Location jh = new Location(0,0,0);
Location fire = new Location(0,0,0);
for (int i = 0; i < R; i++) {
String tmpInput = br.readLine();
for (int j = 0; j < C; j++) {
char c = tmpInput.charAt(j);
if (c == 'J') {
jh = new Location(i, j, 0);
isVisited[i][j] = true;
}
else if (c == 'F') {
q.add(new Location(i, j, 0));
burnedTime[i][j] = 1; //어차피 못가므로 1로 처리
}
map[i][j] = c;
}
}
// fire 먼저 이동
q.add(fire);
while(!q.isEmpty()) {
Location cur = q.poll();
int nextTime = cur.time + 1;
for (int idx = 0; idx < 4; idx++) {
int mx = cur.x + dx[idx];
int my = cur.y + dy[idx];
if (isValid(mx, my) && map[mx][my] == '.' && burnedTime[mx][my] < 1) {
burnedTime[mx][my] = nextTime;
q.add(new Location(mx, my, nextTime));
}
}
}
// 지훈이 이동
int answer = Integer.MAX_VALUE;
q.add(jh);
while(!q.isEmpty()) {
Location cur = q.poll();
int nextTime = cur.time + 1;
// 탈출 성공
if (isEdge(cur.x, cur.y)) {
answer = Math.min(answer, nextTime);
continue;
}
for (int idx = 0; idx < 4; idx++) {
int mx = cur.x + dx[idx];
int my = cur.y + dy[idx];
if (isValid(mx, my) && !isVisited[mx][my] && map[mx][my] == '.') {
// 불이 없거나, 나중에 타거나
if (burnedTime[mx][my] < 1 || burnedTime[mx][my] > nextTime) {
isVisited[mx][my] = true;
q.add(new Location(mx, my, nextTime));
}
}
}
}
System.out.print(answer != Integer.MAX_VALUE ? answer : "IMPOSSIBLE");
}
static boolean isValid(int x, int y) {
return x >= 0 && y >= 0 && x < R && y < C;
}
static boolean isEdge(int x, int y) {
return x == 0 || y == 0 || x == R - 1 || y == C - 1;
}
}
지훈이가 불에 타지 않고 탈출할 수 있다면 몇 분걸린지를 출력하고, 할수없다면 IMPOSSIBLE을 출력하는 문제입니다.
지훈이를 이동시키기 전에, 각 인덱스에 불이 몇분에 퍼지는지를 기록해두기 위해 불을 먼저 퍼뜨립니다.
이후 지훈이가 이동할 때, 불이 없거나, 지훈이가 도달하는 시점보다 뒤에 불이 붙는다면, 이동할 수 있다고 판단할 수 있게 됩니다.
위 과정을 통해 맵에 가장자리에 지훈이가 도달하게 된다면, 카운트의 +1 값을 정답에 누적시켜주면 해결할 수 있습니다.
입력값으로 불이 여러개 들어올 수도 있다는 점을 고려하지 못해서, 몇 번틀렸습니다 ㅠ 아직도 문제를 꼼꼼히 못읽네요..