문제 보러 가기
이번문제는 4179번: 불! 문제와 같다.
문제
상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.
매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.
빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.
각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)
다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.
- '.': 빈 공간
- '#': 벽
- '@': 상근이의 시작 위치
- '*': 불
각 지도에 @의 개수는 하나이다.
출력
각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.
예제 입력 1
5
4 3
####
#@.
####
7 6
###.###
##.##
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....#
#@....#
.######
5 5
.....
..
.@.
..
.....
3 3
###
#@#
###
예제 출력 1
2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
이번문제는 이전 "4179번: 불!" 문제와 같고 테스트 케이스 T만 추가되었다.
이전에 푼 문제라서 거침없이 풀었으나 틀렸다. 왜 틀렸는지 알아보자
아래는 틀린 답이다.
import sys
from collections import deque
dx=[-1,0,1,0]
dy=[0,-1,0,1]
if __name__=="__main__":
T = int(input())
for _ in range(T):
W,H = map(int, input().split())
board = []
dis_P = [[0]*W for _ in range(H)] # 사람의 이동시 시간 기록표
dis_F = [[0]*W for _ in range(H)] # 불의 번짐 이동 시간 기록표
PQ=deque()
FQ=deque()
flag=0
for h in range(H):
board.append(input())
for w in range(W):
if board[h][w]=='@': # 사람있는 곳
dis_P[h][w]=1
PQ.append((h,w))
elif board[h][w]=='*': # 불 난곳
dis_F[h][w]=1
FQ.append((h,w))
# 먼저 불이 퍼지는 시간을 기록한다
while FQ:
h,w=FQ.popleft()
for i in range(4):
nh=h+dx[i]
nw=w+dy[i]
if 0<=nh<H and 0<=nw<W:
if board[nh][nw]!='#' and dis_F[nh][nw]==0: # 건물안, 벽이 아닌곳, 한번도 방문안한곳
dis_F[nh][nw]=dis_F[h][w]+1 # 불이 처음 난시간(1)에서 점차 시간을 추가함
FQ.append((nh,nw))
while PQ:
h,w=PQ.popleft()
for i in range(4):
nh=h+dx[i]
nw=w+dy[i]
if 0<=nh<H and 0<=nw<W:
if board[nh][nw]!='#' and dis_P[nh][nw]==0:
if dis_P[h][w]+1 < dis_F[nh][nw]: # 앞으로 이동할 곳에 불이 번진 시간보다 작아야지만
dis_P[nh][nw]=dis_P[h][w]+1 # 이동해서 기록을 남길수 있다.
PQ.append((nh,nw))
else:
print(dis_P[h][w]) # 건물에서 벗어날때 값 출력
flag=1
break
if flag==0:
print('IMPOSSIBLE')
아래는 정답이다.
import sys
from collections import deque
dx=[-1,0,1,0]
dy=[0,-1,0,1]
if __name__=="__main__":
T = int(input())
for _ in range(T):
W,H = map(int, input().split())
board = []
dis_P = [[0]*W for _ in range(H)]
dis_F = [[0]*W for _ in range(H)]
PQ=deque()
FQ=deque()
flag=0
for h in range(H):
board.append(list(input()))
for w in range(W):
if board[h][w]=='@': # 사람있는 곳
dis_P[h][w]=1
PQ.append((h,w))
elif board[h][w]=='*': # 불 난곳
dis_F[h][w]=1
FQ.append((h,w))
# 먼저 불이 퍼지는 시간을 기록한다
while FQ:
h,w=FQ.popleft()
for i in range(4):
nh=h+dx[i]
nw=w+dy[i]
if 0<=nh<H and 0<=nw<W: # 건물안
if board[nh][nw]!='#' and dis_F[nh][nw]==0: # 벽이 아닌곳, 한번도 방문안한곳
dis_F[nh][nw]=dis_F[h][w]+1
FQ.append((nh,nw))
# 다음 사람의 이동 위치시 시간을 기록한다
while PQ:
h,w=PQ.popleft()
for i in range(4):
nh=h+dx[i]
nw=w+dy[i]
if 0<=nh<H and 0<=nw<W: # 건물안
if board[nh][nw]!='#' and dis_P[nh][nw]==0: # 벽이 아닌곳, 처음 방문하는곳
if dis_F[nh][nw]==0 or dis_P[h][w]+1 < dis_F[nh][nw]: # 불기록지가 0인곳(즉, 불이 나지 않은곳) 또는 불이 난곳의 시간보다 적은 사람의 이동 시간
dis_P[nh][nw]=dis_P[h][w]+1
PQ.append((nh,nw))
else:
print(dis_P[h][w])
flag=1
break
if flag==1: # 이걸 추가해야했다. 위에서 for문 break이후 while break를 위해
break
if flag==0:
print("IMPOSSIBLE")
다 알고 다 푼 문제였는데 ㅠㅠ break때문에...
꼼꼼히 풀자
