[백준] 5427번 불

 화재가 발생한 빌딩(2차원 배열)에 갇힌 사람을 탈출 시키는 문제 입니다. 불이 옮기는 시점과 사람을 이동시키는 시점을 잘 분류해서 쉽게 해결하였습니다. BFS를 이용해서 사람이 이동 가능한 위치를 찾아서 이동 시키고 화재가 퍼질 수 있는지 확인하여 불이 번지도록 만들었습니다. 사람이 탈출 할 수 있는 최단경로를 찾아야하기 때문에 BFS를 사용 하였습니다. 아래는 문제 링크와 소스 코드 입니다.

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

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class EscapeFireBuilding {

	int testNum;
	int[] row, col;
	char[][][] map;
	int[] ans;
	Pair<Integer, Integer>[] sPos;
	int[] dRow = { 0, 0, -1, 1 }, dCol = { -1, 1, 0, 0 };
	
	boolean isArrayBound(int nRow, int nCol, int testNum) {
		if (0 <= nRow && nRow < row[testNum] && 0 <= nCol && nCol < col[testNum]) {
			return true;
		} else {
			return false;
		}
	}

	void bfs(int testNum) {
		Queue<Pair<Integer, Integer>> q = new LinkedList<Pair<Integer, Integer>>();
		Pair<Integer, Integer> tempPair;
		Iterator<Pair<Integer, Integer>> itr;
		int nRow, nCol;
		int tRow, tCol;
		int move = 0;
		boolean die = false;

		q.add(sPos[testNum]);

		for (int i = 0; i < row[testNum]; i++) {
			for (int j = 0; j < col[testNum]; j++) {
				if (map[i][j][testNum] == '*') {
					tempPair = new Pair<Integer, Integer>(i, j, -1);
					q.add(tempPair);
				}
			}
		}
		
		while (!q.isEmpty()) {
			tempPair = q.poll();
			tRow = tempPair.x;
			tCol = tempPair.y;
			move = tempPair.move;
			if (map[tRow][tCol][testNum] == '@') {
				for (int i = 0; i < 4; i++) {
					nRow = tRow + dRow[i];
					nCol = tCol + dCol[i];
					if (isArrayBound(nRow, nCol, testNum)) {
						if (map[nRow][nCol][testNum] == '.') {
							map[nRow][nCol][testNum] = '@';
							tempPair = new Pair<Integer, Integer>(nRow, nCol, move + 1);
							q.add(tempPair);
						}
					} else {
						System.out.println(move + 1);
						return;
					}
				}
			}
			
			if (map[tRow][tCol][testNum] == '*') {
				for (int i = 0; i < 4; i++) {
					nRow = tRow + dRow[i];
					nCol = tCol + dCol[i];
					if (isArrayBound(nRow, nCol, testNum)) {
						if (map[nRow][nCol][testNum] != '*' && map[nRow][nCol][testNum] != '#') {
							map[nRow][nCol][testNum] = '*';
							tempPair = new Pair<Integer, Integer>(nRow, nCol, -1);
							q.add(tempPair);
						}
					}
				}
			}
		}
		System.out.println("IMPOSSIBLE");

	}

	void solution() {
		Scanner sc = new Scanner(System.in);
		String s;

		testNum = sc.nextInt();
		row = new int[testNum];
		col = new int[testNum];
		map = new char[1001][1001][testNum];
		ans = new int[testNum];
		sPos = new Pair[testNum];

		for (int i = 0; i < testNum; i++) {
			col[i] = sc.nextInt();
			row[i] = sc.nextInt();
			sc.nextLine();
			for (int j = 0; j < row[i]; j++) {
				s = sc.nextLine();
				for (int k = 0; k < col[i]; k++) {
					map[j][k][i] = s.charAt(k);
					if (map[j][k][i] == '@') {
						sPos[i] = new Pair<Integer, Integer>(j, k, 0);
					}
				}
			}
		}

		for (int i = 0; i < testNum; i++) {
			bfs(i);
		}

	}

	public static void main(String[] args) {
		EscapeFireBuilding m = new EscapeFireBuilding();
		m.solution();
	}

	class Pair<X, Y> {
		X x;
		Y y;
		int move;

		public Pair(X x, Y y, int move) {
			this.x = x;
			this.y = y;
			this.move = move;
		}

	}
}