문제
상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.
매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.
빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.
각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)
다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.
- '.': 빈 공간
- '#': 벽
- '@': 상근이의 시작 위치
- '*': 불
각 지도에 @의 개수는 하나이다.
출력
각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.
예제 입력 1
5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###예제 출력 1
2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class BJ5427 {
static boolean[][] visited;
static char[][] map;
static int[][] moves={{1,0},{-1,0},{0,1},{0,-1}};
static int w,h;
public static class Point{
int x,y,time;
boolean flag;
public Point(int x, int y, int time,boolean flag) {
this.x = x;
this.y = y;
this.time = time;
this.flag=flag;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb=new StringBuilder();
int T=Integer.parseInt(br.readLine());
for(int t=0;t<T;t++){
StringTokenizer st=new StringTokenizer(br.readLine());
w=Integer.parseInt(st.nextToken());
h=Integer.parseInt(st.nextToken());
map=new char[h][w];
visited=new boolean[h][w];
for(int i=0;i<h;i++){
map[i]=br.readLine().toCharArray();
}
int x=0;
int y=0;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(map[i][j]=='@'){
x=i;
y=j;
}
}
}
int result=bfs(x,y);
if(result!=-1){
sb.append(result+"\n");
}else{
sb.append("IMPOSSIBLE\n");
}
}
System.out.print(sb);
}
private static int bfs(int i, int j) {
Queue<Point> queue=new ArrayDeque<>();
for(int x=0;x<h;x++){
for(int y=0;y<w;y++){
if(map[x][y]=='*'){
queue.offer(new Point(x,y,0,true));
}
}
}
queue.offer(new Point(i,j,0,false));
while(!queue.isEmpty()) {
Point p=queue.poll();
if(!p.flag) {
visited[p.x][p.y] = true;
for (int d = 0; d < 4; d++) {
int a = p.x + moves[d][0];
int b = p.y + moves[d][1];
if (a < 0 || a >= h || b < 0 || b >= w) {
return p.time + 1;
}
if (!visited[a][b] && map[a][b] == '.') {
map[a][b]='@';
map[p.x][p.y]='.';
queue.offer(new Point(a, b, p.time + 1,false));
}
}
}
//불 옮겨붙기
else{
for(int d=0;d<4;d++){
int a = p.x + moves[d][0];
int b = p.y + moves[d][1];
if (a < 0 || a >= h || b < 0 || b >= w) continue;
if(map[a][b]=='.' || map[a][b]=='@'){
map[a][b]='*';
queue.offer(new Point(a,b,p.time+1,true));
}
}
}
}
return -1;
}
}BFS 탐색을 이용하여 풀 수 있었지만 약간의 응용이 필요한 문제였다.
우선, 상근이가 건물을 탈출할 수 있는 경로를 찾아야했고, 불 또한 상하좌우로 옮겨붙어야했다.
Queue에 상근이의 위치정보와 불의 위치정보를 모두 넣어 상하좌우로 이동시켜주면서 상근이가 탈출한 시간을 반환해주면 된다.
좌표값 class 생성
public static class Point{
int x,y,time;
boolean flag;
public Point(int x, int y, int time,boolean flag) {
this.x = x;
this.y = y;
this.time = time;
this.flag=flag;
}
}x 좌표값과 y 좌표값, 시간값과 boolean 값을 넣어주는데 이때 flag 값은 상근이인지 불인지 체크하기 위해 넣어주는 변수이다.
불의 확산
Queue<Point> queue=new ArrayDeque<>();
for(int x=0;x<h;x++){
for(int y=0;y<w;y++){
if(map[x][y]=='*'){
queue.offer(new Point(x,y,0,true));
}
}
}
...
//불 옮겨붙기
if(p.flag){
for(int d=0;d<4;d++){
int a = p.x + moves[d][0];
int b = p.y + moves[d][1];
if (a < 0 || a >= h || b < 0 || b >= w) continue;
if(map[a][b]=='.' || map[a][b]=='@'){
map[a][b]='*';
queue.offer(new Point(a,b,p.time+1,true));
}
}
}map에 들어있는 불의 위치값을 모두 queue에 넣어준다.
queue에서 poll한 값의 flag가 true인지 체크한뒤 상하좌우로 불을 퍼트려준다.
이때, 건물벽인 경우에는 불이 퍼지지 않기 때문에 빈 공간이거나 상근이가 있는 위치라면 불이 퍼질 수 있다.
불이 퍼진 뒤에는 map에 불이 옮겨붙었다는 표시를 해주고 queue에 다음 불의 위치를 저장해준다.
상근이의 이동
queue.offer(new Point(i,j,0,false));
while(!queue.isEmpty()){
Point p=queue.poll();
if(!p.flag){
visited[p.x][p.y]=true;
for(int d=0;d< 4;d++){
int a=p.x+moves[d][0];
int b=p.y+moves[d][1];
if(a< 0||a>=h||b< 0||b>=w){
return p.time+1;
}
if(!visited[a][b]&&map[a][b]=='.'){
map[a][b]='@';
map[p.x][p.y]='.';
queue.offer(new Point(a,b,p.time+1,false));
}
}
}
}평소 아는 BFS 탐색의 방식을 이용하면 쉽게 구현할 수 있는 부분이다. 유의할 점은 상하좌우에 불이나 건물벽이 존재하지 않으면 이동할 수 있다는 것이다.
다만 map의 바깥으로 빠져나갔을 때는 다른 BFS 문제와 달리 탈출에 성공했다는 뜻이기 때문에 시간+1 값을 반환해준다.
그것이 아니라면 상근이가 이동했다는 뜻이므로 map의 @, . 값을 갱신해준다.
이후 이동한 좌표값을 큐에 넣어 이 작업을 반복해준다.
주의할 점
순서대로 작업을 진행하면 정답을 맞출 수 있는데 이때 주의해야할 점은 BFS 탐색시 상근이의 위치값을 먼저 큐에 담았을 때, 불이 퍼지기 전에 상근이가 먼저 이동하는 순서가 되어버리기 때문에
사실은 상근이가 이동하지 못하는 경우에도 이동할 수 있게된다.
이 사실을 주의해서 불의 위치값을 먼저 큐에 담아주면 불이 먼저 퍼진 후 상근이가 이동하게 되기 때문에 정답이 나올 수 있게된다.
