개요
- 풀이 시간 : 30분
- 시간 제한 : 1초
- 메모리 제한 : 256 MB
- 기출 : ICPC Northwestern European Regional Contest Benelux Algorithm Programming Contest BAPC 2012 F번
- 링크 : https://www.acmicpc.net/problem/5427
문제
상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.
매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.
빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.
각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)
다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.
- '.': 빈 공간
- '#': 벽
- '@': 상근이의 시작 위치
- '*': 불
각 지도에 @의 개수는 하나이다.
출력
각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.
해결방법
문제 이해하기
이런 문제는 이제 차라리 너무 쉽게 느껴진다. 당연히 DFS/BFS 문제이다. 하지만 시간 초과가 나지 않을까 처음에 고민을 했었다. 왜냐면 테스트케이스가 최대 100개이고, w와 h가 최대 1000이므로 약간은 시간초과가 날 수 있지 않을까 라고 생각했다.
최악의 경우 한번 테스트하는 동안 1,000,000 연산이 필요할 것이고 테스트케이스가 최대 100이므로 부족할 수도 있을거 같은데...(이건 어디까지 이론상이고 실제로는 모든 테스트케이스가 그럴리는 없으니까 넘어가도록 하자)
알고리즘
일단 나는 단순하게 불의 위치를 저장하는 큐와 상근이의 위치를 저장하는 큐를 분리해서 저장한 다음 순서대로 처리를 진행했었다. 근데 굳이 이렇게 할 필요 없었다.
왜냐면 하나의 큐에서 가장 먼저 불의 위치를 저장하고 마지막의 상근이의 위치를 저장하면 그게 한 사이클인 것이다. 이후에는 다시 불의 위치가 저장될 것이고 상근이의 이동가능 위치가 저장될 것이고... 이것이 반복되겠지. 그리고 vistied를 통해 중복을 제거해주면 된다.
Python
내 코드
from collections import deque
import sys
input = sys.stdin.readline
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
def bfs():
cnt = 0 # 시간 경과
while q:
cnt += 1
# 불이 먼저 번지도록 한다.
while fire and fire[0][2] < cnt:
x, y, time = fire.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < h and 0 <= ny < w:
if board[nx][ny] == "." or board[nx][ny] == "@":
board[nx][ny] = "*"
fire.append((nx, ny, time + 1))
while q and q[0][2] < cnt:
# 상근이의 이동할 수 있는 위치를 구한다
x, y, time = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < h and 0 <= ny < w:
if board[nx][ny] == "." and not visited[nx][ny]:
visited[nx][ny] = True
q.append((nx, ny, time + 1))
else:
return cnt
return "IMPOSSIBLE"
if __name__ == "__main__":
t = int(input())
for _ in range(t):
w, h = map(int, input().split())
q = deque() # 상근이의 위치
fire = deque() # 불의 위치
board = []
visited = [[False] * w for _ in range(h)]
for i in range(h):
board.append(list(input().strip()))
for j in range(w):
if board[i][j] == "@":
visited[i][j] = True
q.append((i, j, 0))
elif board[i][j] == "*":
fire.append((i, j, 0))
print(bfs())
조금 아쉽게 푼 경우이다.
추천 코드
from collections import deque
import sys
input = sys.stdin.readline
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
def bfs():
while q:
x, y = q.popleft()
if visited[x][y] != "FIRE":
flag = visited[x][y]
else:
flag = "FIRE"
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < h and 0 <= ny < w:
if visited[nx][ny] == -1 and (
board[nx][ny] == "." or board[nx][ny] == "@"
):
if flag == "FIRE":
visited[nx][ny] = flag
else:
visited[nx][ny] = flag + 1
q.append((nx, ny))
else:
if flag != "FIRE":
return flag + 1
return "IMPOSSIBLE"
if __name__ == "__main__":
t = int(input())
for _ in range(t):
w, h = map(int, input().split())
q = deque()
board = []
visited = [[-1] * w for _ in range(h)]
for i in range(h):
board.append(list(input().strip()))
for j in range(w):
if board[i][j] == "@":
visited[i][j] = 0
start = (i, j)
elif board[i][j] == "*":
visited[i][j] = "FIRE"
q.append((i, j))
q.append(start)
print(bfs())
# 코드 참고 : https://www.acmicpc.net/source/27590432
✍️ 소스코드양도 그렇고 걸리는 시간도 줄어든 것을 알 수 있다. 성공은 했지만 약간 아쉬움이 남는 문제이다.
