09/03 미확인 도착지 BOJ 9370

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

9370번: 미확인 도착지

1. 풀이 

문제 : BOJ 9730 미확인 도착지

알고리즘 유형 : 다익스트라

 

시작점 A에서 T까지 가는 최단 경로중 경유지에 g,h 노드가 있는지 확인하는 문제였다.

맨 처음 풀 때는 최단경로를 지나는 경로중에 g,h가 있으면 출력하도록 했는데

최단 경로가 여러개 있는 경우를 잡지 못해 실패했다.

 

S에 T까지 가는 최단 경로중 g,h가 포함되어 있음을 보장하기 위해선 다음을 만족해야한다.

 

S에서 T까지 가는 최단 경로 = S에서 G까지 가는 최단 경로 + G에서 H까지 가는 최단 경로 + H에서 T까지 가는 최단 경로

 

위의 내용이 G와 H가 바뀌었을때도 성립해야한다.

 

S에서 T까지 가는 최단 경로는 S를 기준으로 다익스트라를 수행

G에서 H까지 가는 최단 경로는 문제 조건에서 주어짐

H나 G에서 T까지 가는 최단 경로는 G, H에 대해 다익스트라를 수행하면 찾을 수 있다.

 

코드는 다음과 같다

import heapq as hq
n_test = int(input())

def Dijistra(s): #s를 기준으로 하는 다익스트라
    q=[]
    dist =[float('inf') for i in range(n+1)]
    dist[s] =0
    hq.heappush(q,(0,s))

    while q:
        weight, vertice= hq.heappop(q)
        if dist[vertice] < weight:
            continue

        for w, ver in adj[vertice]:
            if dist[ver] > w + weight: #현재 거리가 더 짧은 경로라면
                dist[ver]= w+weight
                hq.heappush(q, (w + weight, ver))

    return dist #거리 리스트를 반환한다.


for i in range(n_test):
    n, m, T = map(int, input().split())  # n교차로 m은 도로  t 목적지 후보 갯
    adj = [[] for i in range(n + 1)] #1번부터 n번노드까지 사용
    s, g, h = map(int, input().split())
    de=[]
    # s 시작점 g와 h 사이의 교차로 사이에 있는 도로를 지나갔다.
    # 목적지 후보중  g와 h를 경유하는 최단 경로
    # 최단경로가 g,h를 포함하는 목적지를 찾으면된다.
    # 최단경로가 여러개 있을 수 있다.

    for i in range(m):
        a, b, d = map(int, input().split())
        adj[a].append((d, b))
        adj[b].append((d, a))
        if (a== g and b== h) or (a==h and b==g):
            path_g_h =d
    for i in range(T):
        de.append(int(input()))



    dist_s = Dijistra(s) #시작점에서 모든 노드로의 거리
    dist_h = Dijistra(h) #h에서 모든 노드로의 거리
    dist_g = Dijistra(g) #g에서 모든 노드로의 거리

    path_s_g = dist_s[g] # s에서 g로 가는 최단거리
    path_s_h = dist_s[h] # s에서 h로 가는 최단거리

    answer =[]
    for t in de:
        path_g_t = dist_g[t] #g에서 t로 가는 최단거리
        path_h_t = dist_h[t] #h에서 t로 가는 최단거리
        path_s_t = dist_s[t] #s에서 t로 가는 최단거리
        
        if path_g_t ==float('inf') or path_h_t ==float('inf') or path_s_t ==float('inf'):
            continue
            # 거리값들중 무한대 값이 있으면 연결이 안되있는 노드임으로 불가능

        path_s_g_h_t = path_s_g + path_g_h + path_h_t
        path_s_h_g_t = path_s_h + path_g_h + path_g_t
        

        if (path_s_g_h_t == path_s_t or  path_s_h_g_t == path_s_t):
            answer.append(t)

    answer.sort()

    print(' '.join(map(str, answer)))

 

2. 다른 풀이

wider93님의 코드를 참고했다.

https://www.acmicpc.net/source/17667300

import sys
import heapq
from math import inf
input = sys.stdin.readline

def candy(n, start, edges, targets): 
    distance = [inf] * (n + 1)
    distance[start] = 0
    que = [(0, start)]
    ans = []
    while que:
        d, p = heapq.heappop(que)
        if distance[p] < d:
            continue
            
        if p in targets: #목표 노드를 지나가게 되면
            targets.remove(p) #타겟 셋에서 후보 노드를 제외하고
            if d % 2: #가중치가 짝수인지 아닌지 비교한다.
                ans.append(p)
                if not targets: #타겟이 더 이상 없다면 
                    return sorted(ans) #정답을 정렬해서 반환한다.
                    
        for f in edges[p]:
            if d + edges[p][f] < distance[f]:
                distance[f] = d + edges[p][f]
                heapq.heappush(que, (distance[f], f))
    return sorted(ans)

tc = int(input())
for __ in range(tc):
    n, m, t = map(int, input().split()) 
    s, g, h = map(int, input().split())
    e = [{} for _ in range(n + 1)] # 가중치 값을 받는다.
    for _ in range(m):
        i, j, d = map(int, input().split())
        # 모든 가중치를 2배 해주고
        e[i][j] = 2 * d 
        e[j][i] = 2 * d
    # g에서 h로 가는 노드만 홀수로 만들어준다.
    e[g][h] -= 1
    e[h][g] -= 1
    
    #만약 s에서 t로 가는 최단 경로가 g와 h를 포함하는 경로를 포함해 1개 이상이라면 무조건 g와 h를 선택
    #뿐만 아니라 g와 h를 지나면 가중치 합이 무조건 홀수
    print(*candy(n, s, e, {int(input()) for _ in range(t)}))