[백준_4179번] 불!

https://www.acmicpc.net/problem/4179

4179번: 불!

[문제]

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)  이동한다. 불은 각 지점에서 네 방향으로 확산된다. 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

 

[입력 조건]

 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

 

[코드]

import java.util.*;

class Point_4179 {
	int x,y,count;
	
	public Point_4179(int x, int y, int count) {
		this.x=x;
		this.y=y;
		this.count=count;
	}
	
	public Point_4179(int x, int y) {
		this.x=x;
		this.y=y;
	}
}

public class BaekJoon_4179 {
	static char[][] map;
	static int r,c,result=0;
	static boolean[][] visited;
	static int[] dx= {-1,0,1,0};
	static int[] dy= {0,-1,0,1};
	static Queue<Point_4179> human=new LinkedList<>();
	static Queue<Point_4179> fire=new LinkedList<>();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		r=sc.nextInt();
		c=sc.nextInt();
		
		map=new char[r][c];
		visited=new boolean[r][c];
		
		for(int i=0;i<r;i++) {
			String str=sc.next();
			for(int j=0;j<c;j++) {
				map[i][j]=str.charAt(j);
				
				if(map[i][j]=='J') // 지훈이의 위치
					human.add(new Point_4179(i,j,0));
								
				if(map[i][j]=='F') // 불의 위치
					fire.add(new Point_4179(i,j));
			}
		}
		
		if(move())
			System.out.println(result);
		else
			System.out.println("IMPOSSIBLE");
	}
	
	static boolean move() {
		while(!human.isEmpty()) { // 지훈이가 더이상 이동할 수 없으면 종료
			int size=fire.size();
			
			/*
			 * 지훈이가 불에 타지 않고 탈출해야 하기 때문에 
			 * 불을 먼저 번지게 한 후 지훈이를 이동시킨다.  
			 */
			while(size-->0) { // 불 전파
				Point_4179 p=fire.poll();
				
				for(int i=0;i<4;i++) {
					int nx=p.x+dx[i];
					int ny=p.y+dy[i];
					
					// 맵의 범위를 넘어간 경우에도 패스
					if(nx<0||ny<0||nx>=r||ny>=c) continue;
					
					// 벽이거나 이미 불이 있는 곳은 패스
					if(map[nx][ny]=='#'||map[nx][ny]=='F') continue;
					
					map[nx][ny]='F';
					fire.offer(new Point_4179(nx,ny));
				}
			}
			
			size=human.size();
			
			while(size-->0) { // 지훈이 이동
				Point_4179 p=human.poll();
				
				for(int i=0;i<4;i++) {
					int nx=p.x+dx[i];
					int ny=p.y+dy[i];
					
					// 지훈이의 경우 맵을 벗어난 경우 탈출에 성공한 것이므로 이동횟수 증가 후 return
					if(nx<0||ny<0||nx>=r||ny>=c) {
						result=p.count+1;
						return true;
					}
					
					// 벽, 불, 이미 방문한 곳은 넘어간다.
					if(map[nx][ny]=='#'||map[nx][ny]=='F'||map[nx][ny]=='J') continue;
					
					map[nx][ny]='J';
					human.add(new Point_4179(nx,ny,p.count+1));
				}
			}
		}
		return false;
	}
}

 

[고찰]

 이번 문제에서 가장 중요한 점은 지훈이가 불에 타지 않고 탈출해야 한다는 점이다. 즉, 지훈이는 앞으로 불이 옮겨갈 칸으로는 이동할 수 없다는 의미이므로 지훈이보다 불을 먼저 이동시키고 지훈이가 이동해야 한다. 이 부분만 신경쓴다면 나머지 부분은 여태까지 많이 풀어봤던 BFS 알고리즘이기 때문에 쉽게 해결 할 수 있는 문제였다.