[백준] 4179 불!

1. 문제

www.acmicpc.net/problem/4179

4179번: 불!

2. 접근방법

최단 시간을 구하는 문제로 아주 일반적인 BFS 문제

 

생각해 볼 것은

불과 지훈이 모두 1분마다 움직이니

불이 번져지는 곳은 지훈이가 갈 수 없다.

그러니 불을 멈져 퍼치고 그 다음 지훈이가 이동을 하는 식으로 짜면 된다.

 

매 분 마다 실행 하는 것은 que의 size를 저장해서 size만큼만 도는 방법으로 구현하였다.

 

3. 자바 코드

package Gold;

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

public class G4_4179불 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		Queue<Point> fire = new LinkedList<Point>();
		Queue<Point> jihun = new LinkedList<>();
		boolean visitF[][] = new boolean[R][C];
		boolean visitJ[][] = new boolean[R][C];
		char map[][] = new char[R][C];
		for (int i = 0; i < R; i++) {
			String S = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = S.charAt(j);
				if (map[i][j] == 'J') {
					jihun.add(new Point(i, j));
					visitJ[i][j] = true;
				}
				if (map[i][j] == 'F') {
					fire.add(new Point(i, j));
					visitF[i][j] = true;
				}
			}
		}
		int dr[] = { 0, 0, 1, -1 };
		int dc[] = { 1, -1, 0, 0 };
		int cnt = 1;
		boolean flag = false;
		gg: while (!jihun.isEmpty()) {
			int size = fire.size();
			for (int s = 0; s < size; s++) {
				Point now = fire.poll();
				for (int i = 0; i < 4; i++) {
					int row = now.x + dr[i];
					int col = now.y + dc[i];
					if (row < 0 || col < 0 || row >= R || col >= C)
						continue;
					if (map[row][col] == '#')
						continue;
					if (visitF[row][col])
						continue;
					visitF[row][col] = true;
					fire.add(new Point(row, col));
				}
			}
			size = jihun.size();
			for (int s = 0; s < size; s++) {
				Point now = jihun.poll();
				if (now.x == 0 || now.x == R - 1 || now.y == 0 || now.y == C - 1) {
					flag = true;
					break gg;
				}
				for (int i = 0; i < 4; i++) {
					int row = now.x+dr[i];
					int col = now.y+dc[i];
					if (row < 0 || col < 0 || row >= R || col >= C)
						continue;
					if (map[row][col] == '#' || visitF[row][col])
						continue;
					
					if (visitJ[row][col])
						continue;
					visitJ[row][col] = true;
					jihun.add(new Point(row, col));
				}
			}
			cnt++;
		}
		System.out.println(flag? cnt : "IMPOSSIBLE ");
	}
}

4. 마치며

교과서 같은 문제.