![]()
밸만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 그래프에 간선이 가중치를 가질 때 최단 거리를 구하는 알고리즘이다. 만약 그래프가 음수 간선을 가질 때 다익스트라 알고리즘 대신 사용하면 된다. 그럼 당연히 드는 의문이 있을 것이다. 다익스트라는 음수 간선이 있을 때 최단 거리를 구하지 못하는가? - 아니다. 꼭 그런 것만은 아니다. 음수 간선이 있어도 다익스트라가 최단 거리를 구할 수 있다. 위에 그래프는 단방향의 간선을 가지고 A->B로 가는 경로가 두 가지가 있다. 그래프를 대충 봐도 우리는 당연하게 A->B로 가는 최단 거리가 -1 임을 알 수 있다. 다익스트라도 이 상황에서는 최단 경로를 구할 수 있고, 결국 그래프에 음수 간선이 있더라도 다익스트라로 무조건 풀 수 없는 건 아니라는 뜻이다...
바이러스 조건에 대한 설명이 참 부족한 문제 같다. 굉장히 많은 사람들을 혼란하게 만든 듯.. 나도 참 이해가 안됐었는데 이렇게 생각하니까 그나마 이해가 됐다. 1. 우리가 구하고자 하는 건 빈 공간에 바이러스가 퍼지는 시간이다. 즉 ( 2 == 활성, * == 비활성, 0 == 빈 공간) 2 0 0 * 이라면, 답은 2초이다. 2. 비활성 바이러스가 활성 바이러스가 되는 데 걸리는 시간은 1초가 맞다. 즉 2 0 * 0 이라면, 답은 3초이다. 3. 비활성 바이러스가 활성 바이러스가 되는데 걸리는 시간은 이런 경우에 고려할 필요가 없다. 즉 2 * * * 이라면, 답은 0초이다. 왜냐하면 승원이가 구하고자 하는 시간은 "빈" 공간에 바이러스(비활성, 활성 상관없음)를 전파시키는데 걸리는 시간이기 때문이..
