Jonyo Programming

[BOJ 1865(G4)리뷰] 벨만포드 알고리즘을 이용하는 문제다. 시간이 되돌아 가는것 = 음의 가중치를 갖는 간선이라고 생각하면 된다. 도로는 양방향으로 이동이 가능하므로 양방향으로 입력을 받고, 웜홀은 단방향이므로 단방향으로 입력을 받는다. 그 후에 벨만포드 알고리즘을 수행하며 사이클이 있는지 확인하여 결과를 출력하면 된다. 나는 이 문제에서 두가지 실수를 했다. 첫째는 MAX값을 INT_MAX값으로 설정하여 거리를 갱신하는 부분에 오버플로우가 나 올바른 결과가 나오지 않았다. 둘째는 방문했던 적이 있던 정점에 대해서만 거리를 갱신하는 작업을 수행했었는데, 만약 시작노드가 다른 노드와 연결되어 있지 않은 노드라면, 나머지 노드는 거리를 갱신할 수 없게된다. 따라서 이 조건을 없애야 한다. 위 두가지..

[BOJ 3860(P5)리뷰] 시작점부터 시작하여 목적지까지 도착해야 한다. 묘지가 있는곳으로는 이동할 수 없으며, 귀신 구멍이라는 특정한 칸으로 이동하면 다른 곳으로 시간을 워프하여 이동할 수 있다. 이때 시간을 과거로 되돌릴 수 있다. 인접한 칸을 간선으로 갖고, 귀신 구멍이라는 특별한 간선을 갖는 그래프라고 생각하면 된다. 다만, 과거로 되돌아 갈 수 있다고 했으니 음의 가중치를 갖는 그래프이다. 문제에서 최단거리를 구하라 했으니 최단거리를 구하는 알고리즘을 사용해야 한다. 시작지와 목적지가 주어져 있으므로 다익스트라 알고리즘이 적합하겠지만, 간선에 음의 가중치가 붙을 수 있으므로 벨만포드 알고리즘을 사용해야 한다. 만약 음의 사이클이 존재하면 "Never"를, 음의 사이클은 존재하지 않지만 목적지..