스스로 작성한 코드 오류 질문드립니다.
234
김유진
작성한 질문수 1
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은 잘 나오지만 다른 케이스는 나오지 않을 것 같네요.
영상의 방법으로 하시기 바랍니다.
기존에 윈도우 10으로 잘 써왔는데 윈도우 11로 바꾸고 나서 채점이 안됩니다.
1
104
2
스택에서 ')'을 만나는 경우
0
112
3
문제가 어디있나요?
0
87
2
변수 or 함수명
0
81
1
침몰하는 타이타닉 문제 질문입니다
0
72
1
AA.py 책점 에러
0
65
1
오늘 구매했는데 파이썬 자료구조 궁금한거 있으면 답변이 잘 될까요.
0
117
2
5.동전분배하기 문제 밑에코드도 정답이될까요?
0
118
1
아나그램 비교 코드
0
126
2
AA.PY파일 복사 후 채점 진행할때 오류 발생합니다.
0
164
2
문제 링크가있나여?
0
155
2
채점기 Time Limit Exceeded 오류 문의
1
183
2
동적계획법은 사용하는 문제
0
135
2
제 코드 좀 봐주세요
0
155
1
예외가 존재할 가능성?
0
100
1
3번이 안풀립니다
0
98
0
5번 틀림
0
125
0
오류원인?
0
106
0
리스트 선언
0
116
1
침몰하는 타이타닉(그리디) 문제 질문
0
115
1
알고리즘
0
74
1
코딩테스트
0
98
1
DFS 순서 질문드립니다.
0
139
2
left, right를 사용한 풀이법에 대한 질문입니다
0
102
1





