-
[BOJ/python]9370번 미확인 도착지점 + 오답 이유알고리즘/BOJ 2022. 8. 9. 21:55
백준 9370번 미확인 도착지점 파이썬
문제 링크 - https://www.acmicpc.net/problem/9370
생각지도 못한 곳에서 계속해서 오답이 발생했다. 아마 나처럼 오답을 받고 검색하는 사람들이 꽤 될 것 같은 문제다.
최단 거리를 이동하면서 h→g 경로를 선택하는 경우가 무엇을 의미하는 지 파악하는 것이 중요하다.
s→g 까지의 최단거리가 s→h→g 인 경우에 h→g 경로를 선택하게 된다. 반대로 s→h 까지의 최단거리가 s→g→h 인 경우에는 g→h 경로를 선택하게 된다.
두 경우를 고려하지 않고 풀 수도 있지만 하나의 테스트 케이스에서 h→g 경로와 g→h 경로 모두 사용할 수 없다는 것도 중요한 사실이다. h→g / g→h 순서를 고려하고 푸는 방법과 경우를 나누지 않고 푸는 방법 모두 가능하다.
이제 목적지 후보 중 어떤 곳에 이동이 가능한 지 파악해야 한다.
t를 목적지 후보 중 하나라고 하자. s→ t 의 최단 거리가 s→h→g→t 인 경우에, h→g 경로를 선택하여 t로 이동할 것이다.
즉, s→t의 최단 거리가 s→h→g→t 혹은 s→g→h→t 인 경우에 h-g 경로를 선택하여 목적지 t로 이동한다.
1. 풀이
- s,g,h에서 시작하는 다익스트라를 통해 각 노드까지의 거리를 구한다.
- s→g 까지의 최단거리 + g-h 거리 + h→t 까지의 최단거리가 s→t 까지의 최단거리와 같다면 목적지 후보t 에 도착할 수 있다.
- 마찬가지로, s→h 까지의 최단거리 + h-g 거리 + g→t 까지의 최단거리가 s→t 최단거리와 같다면 목적지 후보 t에 도착할 수 있다.
- 두 경우 중 하나만 만족하면 answer 배열에 추가한다.
🚨주의 사항
만약 INF=float(’inf’)로 초기화하는 경우 오답이 발생할 수 있다. 만약 s→t 로 이동이 불가능하고 (거리 = INF), h→t 혹은 g→t의 이동도 불가능한 경우 목적지에 도착할 수 없지만, INF + INF = INF 가 되어 정답 처리를 하게 된다는 점을 고려해야 한다.
2.1 3번의 다익스트라 사용 코드
from heapq import heappop, heappush def deijkstra(start): dist = [INF for _ in range(N+1)] dist[start]=0 heap =[] heappush(heap, [0,start]) while heap: weight,node = heappop(heap) if dist[node] < weight: continue for next, cost in G[node]: if dist[next]>weight+cost: dist[next] = weight + cost heappush(heap,[dist[next],next]) return dist INF = int(1e9) T= int(input()) for _ in range(T): N,M,K = map(int, input().split()) s,g,h = map(int, input().split()) G=[[]for _ in range(N+1)] for _ in range(M): u,v,w = map(int, input().split()) if (u==g and v==h) or (u==h and v==g): gToh = w G[u].append([v,w]) G[v].append([u,w]) candidate = {} for _ in range(K): candidate[int(input())]=1 distFromS = deijkstra(s) distFromG = deijkstra(g) distFromH = deijkstra(h) answer = [] for i in candidate: if ( distFromS[g] + gToh + distFromH[i] == distFromS[i] ) or ( distFromS[h] + gToh+ distFromG[i] == distFromS[i] ): answer.append(i) answer.sort() print(*answer)
2.2 2번의 다익스트라 사용 코드
만약 s→h→g 경로를 선택한다면, dist[g] = g-h거리 + dist[h] 일 것이고 s→g→h 경로를 선택한다면, dist[h]= g-h거리 + dist[g] 인 점을 이용하여 두 번의 다익스트라만 계산하여 풀 수 있다.
만약 h→g 경로를 이용한다면, s→g 최단거리 + g→t 최단거리 = s→t 최단거리인 경우에 목적지 후보에 도착할 수 있다.
from heapq import heappop, heappush def deijkstra(start): dist = [INF for _ in range(N+1)] dist[start]=0 heap =[] heappush(heap, [0,start]) while heap: weight,node = heappop(heap) if dist[node] < weight: continue for next, cost in G[node]: if dist[next]>weight+cost: dist[next] = weight + cost heappush(heap,[dist[next],next]) return dist INF = int(1e9) T= int(input()) for _ in range(T): # global N,G N,M,K = map(int, input().split()) s,g,h = map(int, input().split()) G=[[]for _ in range(N+1)] for _ in range(M): u,v,w = map(int, input().split()) G[u].append([v,w]) G[v].append([u,w]) candidate = {} for _ in range(K): candidate[int(input())]=1 distFromS = deijkstra(s) if distFromS[g] > distFromS[h]: newStart = g elif distFromS[g] < distFromS[h]: newStart = h distFromNewS = deijkstra(newStart) answer = [] for i in candidate: if distFromS[newStart] + distFromNewS[i] == distFromS[i]: answer.append(i) answer.sort() print(*answer)
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ/python]1707번 이분 그래프 (1) 2022.08.30 [BOJ/python]1477번 휴게소 세우기 (0) 2022.08.09 [BOJ/python]1655번 가운데를 말해요 (0) 2022.08.08 [BOJ/python]2836번 수상 택시 (0) 2022.07.21 [BOJ/python]2370번 시장 선거 포스터 (0) 2022.07.18