반응형
알고리즘 분류 : 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()
참고
반응형