• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

스스로 작성한 코드 오류 질문드립니다.

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)
    

답변 1

답변을 작성해보세요.

0

안녕하세요^^

BFS에서 

elif days[x][y]+1 < days[nx][ny]: #기존보다 더 빨리 익을 수 있음
                    days[nx][ny]= days[x][y]+1 
                    dq.append((nx,ny))

부분때문에 시간이 너무 많이 걸리는 코드가 된 것같습니다.

사실 BFS는 무조건 최단거리로 탐색하는 알고리즘이므로 위와 같은 코드는 필요없습니다. 그런데 BFS를 여러번 돌리다보니 위와 같은 코드가 필요해보이기는 한데, 그리 좋은 방법은 아닌것 같습니다.

위에 코드를 제거하면 -1은 잘 나오지만 다른 케이스는 나오지 않을 것 같네요.

영상의 방법으로 하시기 바랍니다.