[백준] 1865 웜홀

들어가기 

• 1865. 웜홀은 어떤 node에서 출발해서 출발점으로 다시 되돌아 왔을 때 비용이 음이 되는지를 체크하는 문제입니다.
• 최소 비용 또는 최단거리를 구하는 그래프 문제에서 자주 적용되는 벨만-포드 / 다익스트라 알고리즘이 있습니다.
• 1865.웜홀에는 웜홀이라는 음의 간선이 있기 때문에 벨만 포드 알고리즘을 적용하는 문제입니다.
• 벨만 포드 알고리즘은 잘 정리된 글을참고해주세요.
• 저는 예시를 활용하여 풀이하도록 하겠습니다.

 

풀이

문제의 입력 값을 정리해봅시다.

• 우선 N , M , W의 입력을 받습니다. 
  
  • N은 노드 / M은 간선 / W는 웜홀입니다
• 그리고 M 간선에 대한 입력을 받습니다. S와 E는 연결된 지점의 번호, T는 이 도로를 통해 이동하는데 걸리는 시간을 의미합니다.
• S와 E를 연결한다는 의미에서 양방향에 대한 간선 정보라는 것을 알 수 있습니다.

• 다음은 W 웜홀에 대한 입력을 받습니다. S는 시작 지점, E는 도착 지점, T는 줄어드는 시간을 의미합니다.
  S가 시작점이며 E가 도착 지점이므로 웜홀은 단방향 간선입니다. 그리고 T는 음수입니다.

벨만-포드 알고리즘 적용

• 벨만 포드 알고리즘은 노드의 N-1개만큼 Edge Relaxation을 진행하면서 S에서 E로 가는 비용을 계산합니다.
• 그리고 마지막으로 한 번 더 Edge Relaxation을 진행하여 음의 cycle이 존재하는 지를 확인 할 수 있습니다.
• 1865.웜홀 문제에서는 음의 Cycle이 존재하면 "YES"를 존재하지 않으면 "NO"를 출력합니다.
• 아래는 예시 입력값으로 벨만 - 포드 알고리즘을 적용해보았습니다.

 

• 출발점을 1번 노드로 하였습니다.
• 각 노드에 표기된 녹색은 최소 비용을 나타냅니다.
• cost(s,e) : S노드에서 E노드로 가는 최소비용으로 표시하겠습니다.
• Edge Relaxation의 간선 순서는 상관 없습니다.
• 첫번째 Edge Relaxation
  • c(1,2) : 0 + 2이며, INF > 2이므로 2로 Save
  • c(2,1) : 2 + 2이며 4 > 0이므로 Skip
  • c(2,3) : 2 + 1이며 INF > 3이므로 3로 save
  • c(3,2) : 3+ 1이며 4 > 2이므로 skip
  • c(1,3) : 0 + 4 이며 4 > 3 이므로 skip
  • c(3,1) : 3 + -3이며 0 ==  0 이므로 Skip

첫번째 Edge Relaxation을 마친 노드

• 두번째 Edge Relaxation
  • c(1,2) : 0 + 2이며, 2 == 2이므로 Skip
  • c(2,1) : 2 + 2이며 4 > 0이므로 Skip
  • c(2,3) : 2 + 1이며 3 == 3이므로 3로 Skip
  • c(3,2) : 3+ 1이며 4 > 2이므로 skip
  • c(1,3) : 0 + 4 이며 4 > 3 이므로 skip
  • c(3,1) : 3 + -3이며 0 ==  0 이므로 Skip

두번째 Relaxation을 마친 노드

• 노드의 N-1번 Edge Relaxation을 진행하면 출발점에서 모든 노드까지의 비용은 최소 비용이 적용됩니다.
• 이 상태의 그래프에서 Edge Relaxation을 한 번 더 적용하면 음의 Cycle이 있음을 판별할 수 있습니다.
• N-1번 Edge Relaxation을 적용하면 모든 노드는 최소 비용이 적용된 상태인데 한 번 더 했을 경우 변화가 생기면 음의 Cycle이 있기 때문입니다.
• 위 예시에서는 한번더 Edge Relaxation을 적용하면 변화가 없기 때문에 예시의 정답은 "NO"입니다.
• 이렇게 풀이대로 구현하면 1865. 웜홀을 푸실 수 있습니다.

 

소스