수타.
2023. 10. 1. 00:33
https://www.acmicpc.net/problem/4179
4179번: 불!
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자
www.acmicpc.net
문제요약:
배열안에 사람,벽,불,빈공간 이 존재하고, 사람이 먼저 그후 불이 이동한다. 사람은 상하좌우로 한 칸씩 이동할 수 있고, 불은 상하좌우로 한 칸씩 확산 된다. 사람은 미로의 가장자리 공간에서 탈출이 가능하다고 할때, 탈출이 가능하다면 몇칸을 이동했는지 출력하고 실패했다면, IMPOSSIBLE을 출력하라
소요시간:
40분
난이도:
골드4
제출횟수:
3
코드:
import sys
from collections import deque
input = sys.stdin.readline
r,c = map(int,input().split())
arr = [list(input()) for _ in range(r)]
dy = [-1,0,1,0]
dx = [0,1,0,-1]
def bfs():
move = []
temp = []
for y in range(r):
for x in range(c):
if arr[y][x] == 'J':
temp.append(['J',y,x,0])
if arr[y][x] == 'F':
move.append(['F',y,x,0])
move = deque(temp+move)
while move:
ch,y,x,ans= move.popleft()
if ch == 'J':
if arr[y][x] == 'J':
for i in range(4):
ny = y+dy[i]
nx = x+dx[i]
if 0<=ny<r and 0<=nx<c:
if arr[ny][nx] == '.':
arr[ny][nx] = 'J'
move.append(['J',ny,nx,ans+1])
else:
return ans+1
else:
continue
else:
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if 0<=ny<r and 0<=nx<c and arr[ny][nx] not in ['#','F']:
arr[ny][nx] = 'F'
move.append(['F',ny,nx,0])
return 'IMPOSSIBLE'
print(bfs())
먼저 사람과 불 둘다 똑같이 BFS로 한칸씩 확산을 해서 사람이 벽에 닿으면 return 하고 만약 그렇지 않고 while문이 끝나게 된다면 불가능을 출력했습니다. 이때 2번의 제출을 통해 2개의 오류를 찾았는데, 첫번째 오류는 마지막 불의 확산에서 벽만아니면 확산하게 두었더니, 불일때도 확산을 해서 이러면 불이 왔다갔다 하기 때문에 무한 반복이 된다는점 > 그래서 불 다음 불일땐 확산 X, 두번째 오류는 queue를 통해 자연스럽게 사람이 먼저 이동하고 불이 이동하게 짰는데, 맨처음 위치를 계산할 때, 한 포문에서 한번에 같은 queue에 넣으면, 불이 먼저 발견되면 불부터 이동하기 때문에, 사람은 따로 빼준뒤 맨앞으로 합쳐주었습니다.