글 읽기 - 벨만포드에 질문글에 올린 주의사항들 다 고려한 거 같은데 틀립니다

1. 음수 사이클에 도달할 수 있으면 어차피 출구 못 간다고 해도 never 출력

2. 출구에서는 인접 노드로 가기 금지

3. 아직 한번도 relax가 이루어지지 않아서 현재 dist값이 inf면 완화 시도도 안 하고 넘어가기

4. 귀신구멍은 도움 안된다고 무시할 수 있는 것이 아니니 구멍에서는 인접 노드로 이동 불가

왜 이러는 걸까요. 암만 살펴봐도 모르겠어요.

마지막 음수 사이클 판단 부분이 완전하지 않습니다.

그래프의 간선이 무엇인지 생각해봅시다. 귀신구멍(`rel`)으로 연결된 통로 이외에도, 각 `(y, x)` 마다 `(y + dy[k], x + dx[k])` 점들이 거리 1으로 연결되어있습니다.

따라서 `if dist[y + dy[k]][x + dx[k]] < dist[y][x] + 1` 이라면 `cycle = True` 를 체크하는 과정이 필요합니다.

반례도 첨부해드립니다.

감사합니다.

2 3
0
1
0 2 1 0 -5
0 0

# Expected answer: Never

해결했습니다. 정말 감사합니다.

모든 간선에 대해서 다 검사했어야 했는데 대체 왜 -가 나올 수 있는 간선에 대해서만 검사하면 된다고 생각했을까요 으으

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

Baekjoon Online Judge