-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
스스로 작성한 코드 오류 질문드립니다.
22.04.09 18:54 작성 조회수 127
0
선생님의 풀이처럼 토마토가 있는 경우를 모두 queue에 넣은 다음 bfs를 한번만 하는 것이아니라, 토마토가 있을 때마다 {queue에 넣고 bfs돌리고}를 반복하였습니다. 결과가 -1일때만 while문에 빠져서 답이 안나오는데 무엇이 문제일까요 ㅠㅠ 감사합니다~
import sys
import copy
from collections import deque
from collections import defaultdict
sys.stdin = open("input.txt","rt")
def bfs(i,j):
dq = deque()
days[i][j]=1 #새로운 출발점
dq.append((i,j))
while dq:
x,y = dq.popleft()
for i in range(4):
nx,ny = x+dx[i],y+dy[i]
if 0<=nx<n and 0<=ny<m and nums[nx][ny]==0: #토마토 있음
if days[nx][ny] == 0: #아직 방문X
days[nx][ny] = days[x][y]+1
dq.append((nx,ny))
elif days[x][y]+1 < days[nx][ny]: #기존보다 더 빨리 익을 수 있음
days[nx][ny]= days[x][y]+1
dq.append((nx,ny))
if __name__=="__main__":
m, n = map(int,input().split())
nums = [list(map(int,input().split())) for _ in range(n)] #원래 토마토배열
days = copy.deepcopy(nums) #토마토 익는 데 걸리는 시간
dx = [0,0,-1,1]
dy = [1,-1,0,0]
answer = 0
for i in range(n):
for j in range(m):
if nums[i][j]==1: #원래 토마토있음
bfs(i,j)
#정답계산
tmp = 0
for i in range(n):
for j in range(m):
if days[i][j]==0: #익지 않은 토마토 존재
print(-1)
sys.exit()
elif days[i][j]>tmp: #최대 횟수
tmp = days[i][j]
if tmp ==1: #이미 다 익어있는 경우
print(0)
else:
print(tmp-1)
답변을 작성해보세요.
0
김태원
지식공유자2022.04.15
안녕하세요^^
BFS에서
elif days[x][y]+1 < days[nx][ny]: #기존보다 더 빨리 익을 수 있음
days[nx][ny]= days[x][y]+1
dq.append((nx,ny))
부분때문에 시간이 너무 많이 걸리는 코드가 된 것같습니다.
사실 BFS는 무조건 최단거리로 탐색하는 알고리즘이므로 위와 같은 코드는 필요없습니다. 그런데 BFS를 여러번 돌리다보니 위와 같은 코드가 필요해보이기는 한데, 그리 좋은 방법은 아닌것 같습니다.
위에 코드를 제거하면 -1은 잘 나오지만 다른 케이스는 나오지 않을 것 같네요.
영상의 방법으로 하시기 바랍니다.
답변 1