최상단 노드는 S부터 시작한다.
한 노드 당 간선은 +1, -1, +5 이렇게 세 갈래로 뻗는다.
3개의 간선을 돌면서 계산된 새로운 노드를 큐에 담는다.
이미 방문했거나 계산된 노드가 범위를 넘는다면 큐에 담지 않는다.
<처음 풀이>
from collections import deque
def bfs(N):
q = deque()
q.append(N)
visited[N] = 1
while q:
p = q.popleft()
for x in lst:
if visited[p+x] == 0: # 1 <= p+x <= 10000
dis[p+x] = dis[p] + 1
if p+x == E:
print(dis[p+x])
exit(1) # 처음으로 찾은게 최소임 따라서 출력하고 바로 끝내면 됨
visited[p+x] = 1
q.append(p+x)
S, E = map(int, input().split())
lst = [1, -1, 5]
visited = [0]*10001
dis = [0]*10001
bfs(S)exit code 1 이 났고.. 입력이 7 8945 인 경우는 에러가 났다.
원래는 1790이 출력되어야 하는데 위 코드는 출력이 안되고 끝난다.
1. 우선
if visited[p+x] == 0: 부분에 범위 처리를 안해서 에러가 난 것 같다. 1 <= p+x <= 10000를 추가하여 if (1 <= p+x <= 10000) and visited[p+x] == 0: 로 바꾸었다.
2. 그리고
exit(1) 부분이 문제였다.
exit(0)으로 바꾸니까 성공했다.
둘 차이를 모르고 그냥 아무거나 썼다..😓
💡 exit(1)과 exit(0) 차이점
exit(1): 프로그램을 비정상적으로라도, 강제적으로 종료시키고 싶을 때 사용 - 문제가 있음을 의미하므로 프로그램이 종료
exit(0): 프로그램을 정상적으로 종료시키고 싶을 때 사용 - 문제 없이 프로그램이 종료
<정답 코드>
from collections import deque
def bfs(N):
q = deque()
q.append(N)
visited[N] = 1
while q:
p = q.popleft()
for x in lst:
if (1 <= p+x <= 10000) and visited[p+x] == 0:
dis[p+x] = dis[p] + 1
if p+x == E:
print(dis[p+x])
exit(0) # 처음으로 찾은게 최소임 따라서 출력하고 바로 끝내면 됨
visited[p+x] = 1
q.append(p+x)
S, E = map(int, input().split())
lst = [1, -1, 5]
visited = [0]*10001
dis = [0]*10001
bfs(S)