BOJ 4179 · 불!

알고리즘 분류 : BFS  

불이 도달하기 전에 탈출하는 최단 거리를 구하는 문제다. BOJ 5427번 문제 '불'과 유사하다.

• 불의 좌표를 먼저 큐에 집어 넣는다. 여러 곳이 있을 수 있으며, 모두 먼저 넣어야 한다.
• 불 좌표를 모두 넣었다면, 이후에 사람 좌표를 넣는다.
• BFS 탐색 시작.

---

C++ 소스코드

#include <cstdio>
#include <queue>
using namespace std;

struct fire {
    int x, y, f;
};

int R, C, sx, sy;
char a[1000][1000];
int dist[1000][1000];
queue<fire> q;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void bfs() {
    q.push({sx, sy, 0});
    dist[sx][sy] = 1;
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y, f = q.front().f; q.pop();
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx < 0 || nx >= R || ny < 0 || ny >= C) {
                if (f) continue;
                printf("%d\n", dist[x][y]);
                return;
            }
            if (dist[nx][ny] || a[nx][ny] == '#') continue;
            q.push({nx, ny, f});
            dist[nx][ny] = dist[x][y]+1;
        }
    }
    printf("IMPOSSIBLE\n");
}

int main() {
    scanf("%d %d", &R, &C);
    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            scanf(" %1c", &a[i][j]);
            if (a[i][j] == 'J') sx = i, sy = j;
            else if (a[i][j] == 'F') {
                q.push({i, j, 1});
                dist[i][j] = 1;
            }
        }
    }
    bfs();
    return 0;
}

---

Python 3 소스코드

from sys import stdin
from collections import deque
input = stdin.readline

R, C = map(int, input().split())
a = [list(input().strip()) for _ in range(R)]
dist = [[0]*C for _ in range(R)]
q = deque()
for i in range(R):
    for j in range(C):
        if a[i][j] == 'J':
            sx, sy = i, j
        elif a[i][j] == 'F':
            q.append((i, j, 1))
            dist[i][j] = 1

def bfs():
    q.append((sx, sy, 0))
    dist[sx][sy] = 1
    while q:
        x, y, f = q.popleft()
        for dx, dy in (-1, 0), (0, 1), (1, 0), (0, -1):
            nx, ny = x+dx, y+dy
            if nx < 0 or nx >= R or ny < 0 or ny >= C:
                if f:
                    continue
                print(dist[x][y])
                return
            if not dist[nx][ny] and a[nx][ny] != '#':
                q.append((nx, ny, f))
                dist[nx][ny] = dist[x][y]+1
    print("IMPOSSIBLE")

bfs()

---

참고

• 백준 온라인 저지 : BOJ 4179
• 불