Baekjoon 4179 불! JAVA

 

4179번: 불!

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

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

지훈이와 불은 매 분마다 한 칸씩 수평 또는 수직으로(비스듬하게 이동하지 않는다)  이동한다. 

불은 각 지점에서 네 방향으로 확산된다. 

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

조건

[입력]

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R 줄 동안 각각의 미로 행이 주어진다.

 각각의 문자들은 다음을 뜻한다.

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

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

 

[출력]

지훈이가 불이 도달하기 전에 미로를 탈출할 수 없는 경우 IMPOSSIBLE을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다. 

풀이

해당 문제는 map가 주어질 때 지훈이가 불보다 먼저 미로에 탈출하는 최솟값을 구하는 문제다.

bfs 2개를 이용하여 해결하였고, 코드상에는 dfs라고 잘못 입력하였다... 실수 ㅎ 로직은 아래와 같은 방식으로 구현하였다.

다만 문제에서 불이 이동이 먼저인지 주어지지 않아 먼저 지훈이를 이동시켰더니 50~60 퍼에서 실패하였고, 불을 먼저 이동시키니 통과할 수 있었다.

1. 입력 처리를 하면서 지훈이 큐와 불 큐에 각각 좌표값을 담는다. 지훈이는 이동 횟수 1도 같이 담는다.

2. 불 큐를 한 사이클 이동시킨다. 이때 map를 갱신해서 방문을 체크한다.

3. 지훈이 큐가 비었는지 체크한다.

 3-1. 큐가 비지 않았으면 지훈이를 한 사이클 이동시킨다.

 3-2. 큐가 비었다면 실패한 경우 IMPOSSIBLE를 출력한다.

4. 지훈이 큐를 이동시키면서 도착했는지 체크한다.

5. 위와 같은 로직을 반복한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int R, C, dy[]= {-1,1,0,0}, dx[] = {0,0,-1,1};
	static char[][] map;
	static boolean[][] visit;
	static Queue<Node> jq = new LinkedList<>(); // 지훈이 담을 큐
	static Queue<Node> fq = new LinkedList<>(); // 불 담을 큐
	public static void main(String[] args) throws Exception{
		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];
		visit = new boolean[R][C];
		for (int i = 0; i < R; i++) {
			map[i] = br.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				if(map[i][j] =='J') {
					jq.add(new Node(i,j,1)); // 지훈이의 이동 시작을 1로해서 큐에 담음
					visit[i][j] = true;
				}else if(map[i][j] =='F') {
					fq.add(new Node(i,j));
				}
			}
		}
		boolean check = false; // 지훈이 도착여부 확인 변수
		while(true) {
			fdfs(); // 먼저 불에대해서 큐에서 하나씩 빼내어 이동시켜준다.
			if(!jq.isEmpty()) { // 지훈이 큐가 안비었으면 지훈이큐에서 하나씩 빼내어 이동시켜준다.
				check = jdfs();
			}else { // 지훈이 큐가 비었으면 더이상 이동불가 실패
				System.out.println("IMPOSSIBLE");
				break;
			}
			if(check) // 이미 탈출한상태 반복문 빠져나옴
				break;
			//2. 불큐 확산시킴
			//1. 지훈이 큐에서 값있으면 지훈이 이동시킴
			//1-1. 지훈이 큐 비었으면 종료 (실패)
			
		}
	}
	private static void fdfs() {
		int size = fq.size(); // 한사이클만 돌기위해 최초 큐의 사이즈만큼 반복
		for (int s = 0; s < size; s++) {
			Node n = fq.poll();
			for (int i = 0; i < 4; i++) {
				int ny = n.y + dy[i];
				int nx = n.x + dx[i];
				if(ny < 0 || nx < 0 || ny >= R || nx >= C || map[ny][nx] =='#' || map[ny][nx] =='F') // 벽이거나 불이면 이동불가 map 배열로 방문체크
					continue;
				fq.add(new Node(ny,nx));
				map[ny][nx] = 'F';
			}
		}
	}
	private static boolean jdfs() {
		int size = jq.size(); // 한사이클만 돌기위해 최초 큐의 사이즈만큼 반복
		for (int s = 0; s < size; s++) {
			Node n = jq.poll();
			if(n.y == 0 || n.x ==0 || n.y == R-1 || n.x == C-1) { // 외각선은 총 4군데 잘 체크하기!
				System.out.println(n.n);
				return true;
			}
			for (int i = 0; i < 4; i++) {
				int ny = n.y + dy[i];
				int nx = n.x + dx[i];
				if(ny < 0 || nx < 0 || ny >= R || nx >= C || map[ny][nx] !='.' || visit[ny][nx]) // visit를 이용해 방문 체크
					continue;
				jq.add(new Node(ny,nx,n.n+1));
				visit[ny][nx] = true;
			}
		}
		return false;
	}
	static class Node{
		int y, x, n;
		Node(int y, int x){
			this.y = y;
			this.x = x;
		}
		Node(int y, int x, int n){
			this.y = y;
			this.x = x;
			this.n = n;
		}
	}
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드