글 읽기 - 파이썬 bfs 런타임에러 원인좀 찾아주시면 감사하겠습니다.

chlgnstjrdla 3년 전 0

주어진 test case들은 올바르게 정답이 나오는데 제출시 바로 런타임 에러가 나는 이유를 모르겠습니다. 조금만 도와주시면 감사하겠습니다.

from sys import stdin, setrecursionlimit

setrecursionlimit(10000)

y, x = map(int, stdin.readline().rstrip().split(" "))

dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

g = []
q = []

dist = [[1]*x for _ in range(y)]
visited = [[0]*x for _ in range(y)]

def bfs(x_in,y_in):
    visited[y_in][x_in] = 1
    
    for i in range(4):
        nx = x_in + dx[i]
        ny = y_in + dy[i]
        
        if 0 <= nx < x and 0 <= ny < y:
            if visited[ny][nx] == 0 and g[ny][nx] == 1:
                dist[ny][nx] = dist[y_in][x_in]+1
                q.append([nx, ny])
        
    while len(q) !=0:
        data = q.pop(0)
        bfs(data[0], data[1])

for _ in range(y):
    g.append([int(x) for x in stdin.readline().rstrip()])

bfs(0,0)
print(dist[-1][-1])

knight7024 3년 전 0

setrecursionlimit 제한 때문인 거 같아서 10**6으로 올리고 해보니 시간 초과가 나네요.

knight7024 3년 전 0

딱 한 줄만 추가하시면 맞습니다.

mirusu400 3년 전 0

일반적으로 BFS에서 탐색이 완료되는걸 마킹할때 그 노드에 접근을 완료했을때가 아니라 그 노드를 큐(여기서는 리스트)에 넣을때 마킹해야됩니다.

즉 다시말해서 24번째라인과 25번째라인 사이에 그 노드 탐색이 완료됐다는걸 마킹하는 소스코드를 한줄 추가하시면 됩니다

(setrecursionlimit도 수정해 주시고요)

그나저나 소스코드가 굉장히 독특하네요.. 재귀를 이용한 BFS라니..

chlgnstjrdla 3년 전 0

답변 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 bfs 런타임에러 원인좀 찾아주시면 감사하겠습니다.

chlgnstjrdla 3년 전 0

knight7024 3년 전 0

knight7024 3년 전 0

mirusu400 3년 전 0

chlgnstjrdla 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말