본문 바로가기

Programming/BOJ

BOJ 5427 · 불


알고리즘 분류 : BFS  


BFS를 통해 최소 이동거리를 구하는 문제이다. BOJ 3055번 '탈출'과 유사한 문제이다.

사람(상근)은 건물 밖으로 탈출해야 하고, 불은 인접한 상하좌우로 번진다. 사람은 불이 번진 곳과 불이 다음에 번질 곳으로 이동할 수 없으므로, 불의 위치를 먼저 Queue에 넣고, 이후에 사람의 위치를 Queue에 넣어야 한다.


  • Queue에 불의 위치와 사람의 위치가 모두 들어가므로, 불과 사람을 구분할 flag를 둔다.
  • 빌딩 밖으로 탈출하는 것은, 다음 위치가 주어진 맵의 범위를 벗어나는지 아닌지로 판별하면 된다.
  • 다음 위치가 맵의 범위를 벗어나는지 확인하고, 벗어나면 현재까지 이동한 거리를 답으로 낸다.
  • 다음 위치가 맵의 범위를 벗어나지만, 불이 벗어난 것이라면 무시한다.
  • 이동 거리를 통해 방문 체크를 한다. 다음 위치가 이미 방문한 곳이거나, 벽(#)이라면 무시한다.
  • 여러 개의 테스트케이스가 주어지므로, 변수 초기화에 유의한다.




C++ 소스코드


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

struct building {
    int x, y, f; // f represents fire(1) or human(0).
};

int w, h;
int sx, sy;
char a[1001][1001];
int dist[1001][1001];
queue<building> 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];
            // Out of range. This means escape the building.
            if (nx < 0 || nx >= h || ny < 0 || ny >= w) {
                if (f) continue; // Fire cannot escape.
                printf("%d\n", dist[x][y]);
                while (!q.empty()) q.pop();
                return;
            }
            // Visited, if dist > 0. '#' is a wall.
            if (dist[nx][ny] || a[nx][ny] == '#') continue;
            // Update next position.
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny, f});
        }
   }
   printf("IMPOSSIBLE\n");
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &w, &h);
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                scanf("%1s", &a[i][j]);
                if (a[i][j] == '*') {
                    // Push positions of fire, first.
                    q.push({i, j, 1});
                    dist[i][j] = 1;
                } else if (a[i][j] == '@') {
                    // Push the position of human, after pushing all of fire.
                    sx = i, sy = j;
                    a[i][j] = '.';
                } else dist[i][j] = 0; 
            }
        }
        bfs();
    }
    return 0;
}




Python 3 소스코드


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

for _ in range(int(input())):
    w, h = map(int, input().split())
    a = [list(input().strip()) for _ in range(h)]
    dist = [[0]*w for _ in range(h)]
    q = deque()
    sx, sy = 0, 0
    dx = (-1, 0, 1, 0)
    dy = (0, 1, 0, -1)

    def bfs():
        q.append((sx, sy, 0))
        dist[sx][sy] = 1
        while q:
            x, y, f = q.popleft()
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w:
                    if f is 1:
                        continue
                    print(dist[x][y])
                    return
                if dist[nx][ny] or a[nx][ny] == '#':
                    continue
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny, f))
        print("IMPOSSIBLE")

    for i in range(h):
        for j in range(w):
            if a[i][j] == '*':
                q.append((i, j, 1))
                dist[i][j] = 1
            elif a[i][j] == '@':
                sx, sy = i, j
                a[i][j] = '.'
            else:
                dist[i][j] = 0

    bfs()




참고



태그