📝 문제
💡 풀이 과정
⛓ 사용한 알고리즘 : BFS
매번 두 개의 BFS를 순서대로 수행하며 이동 최솟값을 갱신하는 방식으로 풀 수 있는 문제이다.
아이디어
매 시간마다 불(F)과 지훈(J)이 동시에 4방향으로 움직일 수 있다. 다만 불은 한 번에 4방향으로 동시에 번지지만, 지훈은 4방향 중 한 곳으로만 이동이 가능하므로, 불과 지훈의 좌표를 각각 움직여야 한다. 따라서 불에 대한 BFS를 수행하는 함수와 지훈에 대한 BFS를 수행하는 함수 두 가지를 번갈아가면서 실행해주면 된다.
우선 불과 지훈이 이동 가능한 조건을 살펴야 한다. 불은 벽( # )외에는 모든 위치로 번질 수 있지만, 지훈은 오직 빈칸( . )으로만 이동이 가능하다. 따라서 불을 먼저 번지게 한 후 지훈을 이동시켜야 한다(그렇지 않으면 지훈은 불길이 번질 곳으로 이동하는 경우가 발생할 수 있기 때문).
static void bfs() {
while(!q.isEmpty()) {
fire(); //불이 번지는 함수
move(); //지훈이가 이동하는 함수
}
}이를 위해 맵 정보를 입력받을 때 불의 초기 좌표들과 지훈의 좌표를 각각 큐에 저장해둔다. 이후 두 개의 큐를 이용해서 두 번의 BFS를 실행해주면 된다.
주의할 점
이 때 주의할 점은 일반적인 bfs와 달리 큐에 1개 이상의 좌표가 들어있을 수 있고(지훈도 여러 방향으로 이동하는 경우의 수를 따지게 되면 초기 좌표는 하나이지만 그 이후부터는 여러 개의 좌표가 들어있을 수 있으니까!), 탐색 도중 계속해서 큐에 좌표를 추가하다 보니 무한 루프에 빠질 수 있다. 따라서 처음 큐 사이즈를 저장해두고, 해당 사이즈만큼만 bfs를 수행해야 한다.
이를 코드로 나타내면 다음과 같다. 우선 불이 번지는 과정을 구현한 함수이다.
static void fire() { //불 번지기
for(int i=0,size=flist.size();i<size;i++) {
Point p = flist.poll();
for(int d=0;d<4;d++) {
int ni = p.i+di[d];
int nj = p.j+dj[d];
if(ni<0 || nj<0 || ni>=R || nj>=C) continue;
if(map[ni][nj]=='#' || map[ni][nj]=='F') continue;
flist.offer(new Point(ni,nj,-1));
map[ni][nj]='F';
}
}
}지훈의 이동 코드도 불이 번지는 것과 동일하지만, 좌표 밖으로 이동한다면 탈출에 성공했다는 의미이므로 최소 이동횟수를 갱신시켜준다는 부분에서 차이점을 갖는다.
static void move() { //지훈 이동
for(int i=0,size=q.size();i<size;i++) {
Point p = q.poll();
for(int d=0;d<4;d++) {
int ni = p.i+di[d];
int nj = p.j+dj[d];
if(ni<0 || nj<0 || ni>=R || nj>=C) {
answer = Math.min(answer, p.cnt);
return;
}
if(map[ni][nj]!='.') continue;
q.offer(new Point(ni,nj,p.cnt+1));
map[ni][nj] = 'J';
}
}
}추가로, 방문체크를 따로 하지 않기 위해 맵에 불과 지훈의 이동경로를 각각 표시하며 탐색을 진행했다. 불은 벽 외 J 이나 . 인 곳으로 이동이 가능하고, 지훈은 . 인 곳으로만 이동이 가능하도록 설정하면 별도의 방문체크용 2차원 배열을 만들지 않아도 된다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int R,C,answer;
static char[][] map;
static Queue<Point> q,flist;
static int[] di = {-1,1,0,0};
static int[] dj = {0,0,-1,1};
static void print() {
for(int i=0;i<R;i++) {
for(int j=0;j<C;j++) {
System.out.print(map[i][j]+" ");
}
System.out.println();
}
System.out.println();
}
static void fire() { //불 번지기
for(int i=0,size=flist.size();i<size;i++) {
Point p = flist.poll();
for(int d=0;d<4;d++) {
int ni = p.i+di[d];
int nj = p.j+dj[d];
if(ni<0 || nj<0 || ni>=R || nj>=C) continue;
if(map[ni][nj]=='#' || map[ni][nj]=='F') continue;
flist.offer(new Point(ni,nj,-1));
map[ni][nj]='F';
}
}
}
static void move() { //지훈 이동
for(int i=0,size=q.size();i<size;i++) {
Point p = q.poll();
for(int d=0;d<4;d++) {
int ni = p.i+di[d];
int nj = p.j+dj[d];
if(ni<0 || nj<0 || ni>=R || nj>=C) {
answer = Math.min(answer, p.cnt);
return;
}
if(map[ni][nj]!='.') continue;
q.offer(new Point(ni,nj,p.cnt+1));
map[ni][nj] = 'J';
}
}
}
static void bfs() {
while(!q.isEmpty()) {
fire();
move();
}
}
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];
q = new LinkedList<>();
flist = new LinkedList<>();
for(int i=0;i<R;i++) {
map[i] = br.readLine().toCharArray();
for(int j=0;j<C;j++) {
if(map[i][j]=='F') flist.offer(new Point(i,j,-1));
if(map[i][j]=='J') q.offer(new Point(i,j,1));
}
}
answer = Integer.MAX_VALUE;
bfs();
if(answer==Integer.MAX_VALUE)
System.out.println("IMPOSSIBLE");
else
System.out.println(answer);
}
static class Point {
int i,j,cnt;
public Point(int i, int j, int cnt) {
this.i = i;
this.j = j;
this.cnt = cnt;
}
}
}