BOJ#5427 불
* 문제
* 풀이
큐를 2개 만든 후 불의 위치와 상근이의 위치를 큐에 각각 삽입합니다.
step 하나당 불과 상근이가 한 level만 bfs 탐색할 수 있도록 구성합니다.
결과적으로 상근이가 탈출한 경우 step을 출력하고, 아닌 경우 IMPOSSIBLE을 출력합니다.
- 비슷한 문제 : 3055번 탈출 http://stack07142.tistory.com/search/탈출
탈출과 비슷한 문제입니다. 탈출의 경우에는 입력값의 경우가 적어서 map을 3차원 배열(row, col, 시간)으로 만들었지만
이 문제의 경우에는 입력값이 크기 때문에 맵은 2차원 배열로 유지하였습니다.
* 나의 코드
import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
/**
* BOJ#5427 불
* https://www.acmicpc.net/problem/5427
*/
public class Main {
static final int BLANK = 0;
static final int WALL = -1;
static final int FIRE = -2;
static int h, w;
static int[][] map = new int[1001][1001];
static boolean[][] discovered = new boolean[1001][1001];
static boolean[][] fireDiscovered = new boolean[1001][1001];
static final int[] dRow = {0, -1, 0, 1};
static final int[] dCol = {-1, 0, 1, 0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
while (T-- > 0) {
Queue<Point> queue = new LinkedList<Point>();
Queue<Point> fireQueue = new LinkedList<Point>();
// input
StringTokenizer st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
initMap();
for (int i = 0; i < h; i++) {
String s = br.readLine();
for (int j = 0; j < w; j++) {
char c = s.charAt(j);
switch (c) {
case '.':
map[i][j] = BLANK;
break;
case '#':
map[i][j] = WALL;
break;
case '@':
map[i][j] = BLANK;
queue.add(new Point(i, j));
discovered[i][j] = true;
break;
case '*':
map[i][j] = FIRE;
fireQueue.add(new Point(i, j));
fireDiscovered[i][j] = true;
break;
}
}
}
// solve
int step = -1;
boolean ret = false;
while (!queue.isEmpty() && !ret) {
// step 하나당 불과 상근이가 하나의 레벨만 bfs 탐색하도록 구성
step++;
// fire
if (!fireQueue.isEmpty()) {
int size = fireQueue.size();
for (int i = 0; i < size; i++) {
Point v = fireQueue.poll();
for (int j = 0; j < 4; j++) {
int nextRowFire = v.row + dRow[j];
int nextColFire = v.col + dCol[j];
if (nextRowFire < 0 || nextRowFire >= h || nextColFire < 0 || nextColFire >= w) continue;
if (fireDiscovered[nextRowFire][nextColFire]) continue;
if (map[nextRowFire][nextColFire] == WALL) continue;
map[nextRowFire][nextColFire] = FIRE;
fireDiscovered[nextRowFire][nextColFire] = true;
fireQueue.add(new Point(nextRowFire, nextColFire));
}
}
}
// human
int size = queue.size();
for (int i = 0; i < size; i++) {
Point u = queue.poll();
if (u.row == 0 || u.col == 0 || u.row == h - 1 || u.col == w - 1) {
bw.write(step + 1 + "\n");
ret = true;
break;
}
for (int j = 0; j < 4; j++) {
int nextRow = u.row + dRow[j];
int nextCol = u.col + dCol[j];
if (nextRow < 0 || nextRow >= h || nextCol < 0 || nextCol >= w) continue;
if (discovered[nextRow][nextCol]) continue;
if (map[nextRow][nextCol] == WALL || map[nextRow][nextCol] == FIRE) continue;
discovered[nextRow][nextCol] = true;
queue.add(new Point(nextRow, nextCol));
}
}
}
if (!ret) bw.write("IMPOSSIBLE\n");
} // ~ test case loop
bw.flush();
bw.close();
br.close();
}
static void initMap() {
for (int i = 0; i < h; i++) {
Arrays.fill(map[i], BLANK);
Arrays.fill(discovered[i], false);
Arrays.fill(fireDiscovered[i], false);
}
}
}
class Point {
int row, col;
Point(int row, int col) {
this.row = row;
this.col = col;
}
}
'Algorithm > 그래프 탐색' 카테고리의 다른 글
| BOJ#2665 미로 만들기 (0) | 2017.04.13 |
|---|---|
| BOJ#1194 달이 차오른다, 가자. (0) | 2017.04.13 |
| BOJ#1726 로봇 (4) | 2017.04.12 |
| BOJ#7569 토마토 (0) | 2017.04.11 |
| BOJ#2667 단지번호붙이기 (0) | 2017.04.10 |