codingismylife   1년 전

안녕하세요! 지금까지 위상 정렬, 다익스트라, 플로이드까지 다 공부하고 오늘 처음 벨만 포드를 공부하고 타임머신 문제를 풀고 바로 이 문제를 풀려니까 잘 안됐습니다

그러다가 게시판을 보고 힌트를 얻어서 그냥 음의 순환을 확인하는 거구나 하고 dist[1] = 0으로 임의의 점을 잡고 벨만 포드를 돌리는 코드를 짰더니 오답이 나와서, 그래프가 연결되어 있지 않을 수 있겠다는 생각을 하고, 그냥 웜홀의 시작 지점의 거리를 모두 0으로 두고 벨만 포드를 돌려서 AC를 받았습니다

다른 분들 코드 보니까 dist[1] = 0으로 해도 답이 나오시는 거 같던데, 제 코드는 왜 이렇게 하면 오답이 나오고, 웜홀의 시작 지점을 모두 0으로 설정해야 정답이 나오는지 잘 모르겠습니다 

그리고 임의의 지점에서 시작해도, 음의 순환이 발생한다는 사실에는 변함이 없는 건가요?? 오늘 처음 공부해서 이해력이 떨어지는 점 양해부탁드립니다 ㅠㅠ 배워가려고 합니다 감사합니다

not_strober   1년 전

질문자님의 이해에 도움이 될 jh님의 글이 있어 공유합니다.

글에도 나와 있는 내용이지만, dist[1] = 0으로 둔 코드가 AC를 받는 이유는 그것들이 질문자님의 코드와 다르게 dist[start]가 LONG_MAX인지 검사를 하지 않기 때문입니다.
dist[start] == LONG_MAX라면 출발점 s에서 start까지 도달하는 경로가 발견되지 않았다는 뜻입니다. 따라서 start -> end로의 완화(relaxation)가 일어나선 안 됩니다.
그러나 이 조건을 검사하지 않으면 s에서 start로의 경로가 존재하고 그 거리가 LONG_MAX인 것으로 취급되어 start -> end의 간선이 음의 가중치를 갖는다면 완화가 발생합니다. 그러므로 그래프에 음수 사이클이 존재한다면 N번째 반복에서 추가로 완화가 일어나 이 문제에서의 올바른 답인 YES를 판정합니다. 하지만 이것은 틀린 구현입니다.
말씀하신 대로 질문자님의 코드에서 dist[1]만 0으로 두면 1번 지점에서 도달 불가능한 음수 사이클을 찾을 수 없으므로 틀립니다. 따라서 질문자님처럼 dist1 벡터를 모두 0으로 초기화하면 이는 가상의 슈퍼 소스 S에서 모든 정점으로 가중치 0인 간선을 잇는 것과 동치이며, 모든 정점을 시작점으로 취급하므로 올바른 풀이가 됩니다.

마지막 질문에 대해서는, 음수 사이클의 존재 자체는 시작점과 무관합니다. 하지만 벨만-포드는 시작점에서 도달 가능한 음수 사이클만 찾을 수 있습니다.

codingismylife   1년 전

정말 감사합니다! 글 읽고 벨판 - 포드에 대한 이해도를 더 높여야겠습니다^^

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