백준 4179 불!

백준 4179 불!

1. 문제 링크

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

4179번: 불!

 

2. 문제 해결에 대한 아이디어

1. Input에서 지훈이의 위치와 불의 위치를 각각 jQ, fQ에 저장한다. --> BFS를 하기 위함

2. 한 턴마다 지훈이와 불이 움직인다.

3. 지훈이는  jMove 불은 fireMove로 각각 구현했다.

   . 나는 지훈이를 먼저 움직이고 그다음에 불을 확산시켰다.

   . n+1번째 턴에 지훈이가 있을 수 있는 위치(이동 전) 중, n번째 턴에 불이 위치한 곳은 제외시켰다.

   . 이동할 수 있는 공간이 없다면, jMove에서 jQ의 크기가 0일 것이다.

   . 탈출하게 된다면 지훈이의 위치는 배열을 벗어난 위치일 것이다.

 

3. 코드

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

public class Main {
	static char[][] board;
	static boolean[][] visited;
	static int[] dirY = { 0, 0, 1, -1 };
	static int[] dirX = { 1, -1, 0, 0 };
	static Queue<Pair> jQ = new LinkedList<>();
	static Queue<Pair> fQ = new LinkedList<>();
	static int R, C, count = 0;

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

		String[] rc = br.readLine().split(" ");

		R = Integer.parseInt(rc[0]);
		C = Integer.parseInt(rc[1]);

		board = new char[R][C];
		visited = new boolean[R][C];

		for (int i = 0; i < R; i++) {
			String line = br.readLine();
			for (int j = 0; j < C; j++) {
				board[i][j] = line.charAt(j);
				if (board[i][j] == 'J')
					jQ.add(new Pair(i, j));
				else if (board[i][j] == 'F')
					fQ.add(new Pair(i, j));
			}
		}

		while (true) {
			count++;
			int status = jMove();

			if (status == 1) {
				System.out.println(count);
				return;
			} else if (status == -1) {
				System.out.println("IMPOSSIBLE");
				return;
			} else {
				fireMove();
			}
		}
	}

	static int jMove() {

		Queue<Pair> tempQ = new LinkedList<>();

		while (!jQ.isEmpty()) {
			Pair now = jQ.poll();
			int y = now.y;
			int x = now.x;
			if (board[y][x] == 'F')
				continue;
			visited[y][x] = true;

			for (int i = 0; i < 4; i++) {
				int yy = y + dirY[i];
				int xx = x + dirX[i];

				// 탈출한 경우
				if (yy < 0 || xx < 0 || yy >= R || xx >= C)
					return 1;

				if (board[yy][xx] == '#' || board[yy][xx] == 'F' || visited[yy][xx])
					continue;
				visited[yy][xx] = true;
				board[yy][xx] = 'J';
				tempQ.add(new Pair(yy, xx));
			}

		}
		// 사방이 불이거나 벽일 경우에는 이동하지 못 했기 때문에 tempQ는 비어있다.
		if (tempQ.isEmpty())
			return -1;

		// 정상적으로 이동한 경우
		jQ = tempQ;
		return 0;
	}

	static void fireMove() {
		Queue<Pair> tempQ = new LinkedList<>();
		while (!fQ.isEmpty()) {
			Pair now = fQ.poll();
			int y = now.y;
			int x = now.x;
			for (int i = 0; i < 4; i++) {
				int yy = y + dirY[i];
				int xx = x + dirX[i];

				if (yy < 0 || xx < 0 || yy >= R || xx >= C 
						|| board[yy][xx] == '#' || board[yy][xx] == 'F')
					continue;
				board[yy][xx] = 'F';
				tempQ.add(new Pair(yy, xx));

			}
		}

		fQ = tempQ;
	}
}

class Pair {
	int y, x;

	public Pair(int y, int x) {
		super();
		this.y = y;
		this.x = x;
	}
}

 

4. 채점 결과

 

5. 느낀 점

1. 지훈이와 불이 한 턴에 모두 움직여야 하는 부분에서 누가 먼저 움직일 것인지를 고민했다.

2. 예시로 주어진 입력에서 지훈이와 불이 붙어있는 경우 불이 먼저 움직이면 구현이 힘들 것이라고 생각했다.

3. 따라서 지훈이를 먼저 이동시키고 그 후 불을 이동시켰다.

4. 처음에는 지훈이가 이동할 수 있는 위치에 마킹한 후 불이 그 위치에 도달할 거라는 생각을 못해 조금 헤맸다.