[백준] 9370번 미확인 도착지(feat. 다익스트라)

https://www.acmicpc.net/problem/9370

 

문제 분석

• 첫 번째 단계(문제 요약 및 조건 파악하기)

처음에, 이 문제를 읽고, 한번에 머리에 안들어와서 당황했다. 입력도 은근히 많았고 말이다.
호흡을 가다듬고, 다시한번 집중해서 읽으면서 중요한 부분을 요약했다.

이해하고나니, 별거 아니었다.

정리하자면, 
s 지점에서 출발하고, 
목적지 후보들이 있고, 
목적지에는 최단 거리로 가야한다. 
경로와 관련된 조건이 있는데, g와 h 교차로 사이에 있는 도로를 무조건 지나가는 경로여야 한다.

목적지 후보들 중, 목적지로 불가능한 경우를 제외하고, 다른 목적지들을 공백으로 분리시켜 오름차순의 정수로 출력해야 하는 문제다.

입력을 풀어서 정리하면 아래와 같다.

테스트케이스 개수
n(교차로), m(도로), t(목적지 후보의 개수)
s(예술가들의 출발지), g(g와), h(h의 교차로 사이에 있는 도로를 지나감을 의미)
이후 m개의 줄마다 3개의 정수 a, b, d가 주어진다. a와 b사이에 길이 d의 양방향 도로가 있다는 뜻이다.
그다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. (모두 서로 다른 위치이며, s와 같지 않다.)
* 첫째 줄을 제외하고는, 테스트 케이스 개수 만큼 반복되는 입력

 

• 두 번째 단계 (문제의 핵심 파악 하기)

문제의 핵심은, s에서 출발해서 목적지 후보들 까지 g와 h 교차로 사이에 있는 도로를 지나가야 하면서 최단거리여야 한다는 것이다.

g와 h 교차로 사이의 도로를 지나야 한다는 것은,
교차로 g와 h를 무조건 지나야함을 의미한다.

목적지에는 최단거리로 간다고 했으므로, g와 h를 지나더라도, 최단 거리여야 할 것이다.

그렇다면 우선, s에서 출발해서 g와 h를 지나서 목적지 후보t[] (목적지가 여러개일 수 있음) 에 도달하는 방법을 생각 해봐야 한다.

• 출발지점 s -> 교차로 g -> 교차로 h -> 목적지t[]
• 출발지점 s -> 교차로 h -> 교차로 g -> 목적지t[] 

이렇게 두가지 방법이 존재 할 것이다.

그렇다면, 각 목적지후보들에 대하여, 이 두가지 방법으로 최단 거리를 구해주고, 
두 가지 방법으로 구한 최단 거리를,
실제로 출발지s -> 목적지후보 t[] 까지의 최단거리와 비교하여,
해당 최단거리가 두 가지 방법으로 구한 최단 거리 중 하나라도, 출발지s -> 목적지 후보t[]까지의 거리와 같다면,
출발지 s에서 출발하여 g와 h를 지나더라도 해당 목적지까지 최단거리로 갈 수 있는 방법이 존재하는 것이므로, 
해당 목적지 후보는, 실제 목적지로 가능하다고 확신할 수 있다.

 

코드를 작성하기 전에, 고민 과정을 comment로 남겼다.

'''
s 지점에서 출발
목적지 후보들 중 하나가 목적지
최단거리로 갈 것

g와 h 교차로 사이에 잇는 도로를 지나갔음

테스트케이스 개수
n(교차로), m(도로), t(목적지 후보의 개수)
s(예술가들의 출발지), g(g와), h(h의 교차로 사이에 있는 도로를 지나감을 의미)
이후 m개의 줄마다 3개의 정수 a, b, d가 주어진다. a와 b사이에 길이 d의 양방향 도로가 있다는 뜻이다.
그다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. (모두 서로 다른 위치이며, s와 같지 않다.)

i)
g와 h를 무조건 지나야 한다면 두가지 방법이 있다.

출발지점 -> g -> h -> 도착지점
출발지점 -> h -> g -> 도착지점

이 두가지의 최단 거리를 구해주고, 이 최단거리 중 하나라도,
출발지점 -> 도착지점의 최단거리와 같은 경우,
해당 도착 지점을 저장해준다.

'''

 

 

코드 작성

import sys
import heapq

# distance 테이블 초기화 하기 위한 INF 선언
INF = int(sys.maxsize)

# 테스트 케이스 개수 T
T = int(sys.stdin.readline().rstrip())

# 다익스트라 함수 작성
def dijkstra(start):
    heap = []
    heapq.heappush(heap, [0, start])    # heap에 heqpq.heappush로 [0, start] 넣어줌
    distance = [INF] * (n + 1)  # distance 테이블 초기화
    distance[start] = 0 # distance 테이블의 start 인덱스에 해당하는 가중치(거리) 값을 0으로 초기화

    while heap: # heap에 데이터가 존재하지 않을 때 까지 반복
        weight, now = heapq.heappop(heap)
        for node_x, node_x_w in graph[now]:
            cost = node_x_w + weight
            if cost < distance[node_x]:
                distance[node_x] = cost
                heapq.heappush(heap, [cost, node_x])
    return distance

for _ in range(T):
    n, m, t = map(int, sys.stdin.readline().rstrip().split())
    s, g, h = map(int, sys.stdin.readline().rstrip().split())
    graph = [[] for _ in range(n + 1)]

    for _ in range(m):
        a, b, d = map(int, sys.stdin.readline().rstrip().split())
        graph[a].append([b, d])
        graph[b].append([a, d])

    x = []
    for _ in range(t):
        x.append(int(sys.stdin.readline().rstrip()))

    s_cost = dijkstra(s)
    g_cost = dijkstra(g)
    h_cost = dijkstra(h)
    answer = []

    for i in x:
        # 출발지점 -> g -> h -> 도착지점 이 경로의 가중치가 출발지점 -> 도착목표 i까지의 가중치와 같거나 or 출발지점 -> h -> g -> 도착지점 이 경로의 가중치가 출발지점 -> 도착목표 i까지의 가중치와 같으면
        if s_cost[g] + g_cost[h] + h_cost[i] == s_cost[i] or s_cost[h] + h_cost[g] + g_cost[i] == s_cost[i]:
            answer.append(i)    # 정답 리스트에 저장

    answer.sort()
    for i in range(len(answer)):
        print(answer[i], end=' ')
    print()

 

아무리 복잡해 보이는 입력이더라도, 이해하고나면 별거 없다. 
두려워 하지말자.