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