백준 1865 - 웜홀 (WA, 오답 원인)
https://www.acmicpc.net/problem/1865
1865번: 웜홀
첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500),
www.acmicpc.net
플로이드 워셜 알고리즘으로 해결 가능하다. 코드가 어렵지도 않다. 최단 경로 탐색을 수행하다가 graph[i][i]가 음수 값이 나오면 음수 사이클이 발견되었다고 보고 true를 반환하면 된다. 사실 이 문제가 정답률이 낮은 이유는 문제가 어렵다기보다 문제 설명에 혼동(내가 실수한 거 맞음)의 여지가 있기 때문인 듯 하다.
1. 출발 위치는 1번 지점이 아닐 수 있다.
어떤 알고리즘을 사용했든 간에, 수행 후 i = 1~|V|에 대해 graph[i][i]의 가중치를 확인해야한다.
2. 웜홀의 시간 감소량도 양수로 입력된다.
입력받은 후 -를 곱하든 따로 처리를 하든 간에 초기값이 양수임을 기억하자.
3. 웜홀은 단방향이고, 도로는 양방향이다.
도로는 u->v, v->u 모두 연결해주자. 이걸 몰라서 30분 더 앉아 있었다.
4. 두 지점을 연결하는 도로가 한 개보다 많을 수도 있다. 이 말은 문제에도 있고 다른 문제들에도 나오긴 하는데, 이 유형을 처음 풀 때는 이것때문에 자주 틀린다. 이미 입력받은 graph[u][v]와 크기를 비교해야 한다.
사실 이 문제는 음수 사이클을 처리할 수 있는 벨만 포드 알고리즘으로 풀어야 한다는데, 플로이드 워셜 알고리즘은 음수 사이클을 제대로 처리할 수는 없지만 감지는 할 수 있다. 따라서 이 문제에서 적용 가능하다.