[백준] 9370 미확인 도착지

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

최단거리로 이동을 하기 때문에 다익스트라를 이용하여 풀이했습니다.

 

최초 풀이시 각 노드로 이동하는 최단 경로를 저장하였습니다.

메모리 초과 문제가 발생하여, 출발지, g, h 노드에서 출발하는 최단 거리를 모두 구해주었습니다. 

2) 알고리즘

• 다익스트라

3) 풀이 코드

사용 언어 - Python

import sys
import heapq
sys.stdin = open('input.txt')

def solution(start):
    heap = [(0, start)]
    distance = [-1] * (n+1)                                         # 반환할 최단 거리

    while heap:
        node = heapq.heappop(heap)
        if distance[node[1]] == -1:                                 # 도착하지 않았으면
            distance[node[1]] = node[0]                             # 최단 거리 갱신

            for next in linked[node[1]]:
                heapq.heappush(heap, (next[0]+node[0], next[1]))    # 다음 탐색
    
    return distance


T = int(sys.stdin.readline())

for _ in range(T):
    n, m, t = map(int, sys.stdin.readline().split())        # 교차로, 도로, 목적지 개수
    s, g, h = map(int, sys.stdin.readline().split())        # 출발지, 두개의 노드

    linked = [[] for _ in range(n+1)]                           # 연결 관계
    answers = []                                                # 정답

    for _ in range(m):                                          # 연결 관계 정리
        a, b, d = map(int, sys.stdin.readline().split())
        linked[a].append((d, b))                                # (거리, 도착 노드)
        linked[b].append((d, a))

    targets = {int(sys.stdin.readline()) for _ in range(t)}     # 목적지 노드 목록

    distance_s = solution(s)            # 출발지, g, h 에서 도착 노드까지의 최단 거리
    distance_g = solution(g)
    distance_h = solution(h)

    for target in sorted(targets):      # 출발지->g(h)->h(g)->도착지 의 부분별로 구한 거리가 최단거리인 경우
        if distance_s[g] + distance_g[h] + distance_h[target] == distance_s[target] or\
            distance_s[h] + distance_h[g] + distance_g[target] == distance_s[target]:
            answers.append(target)
    
    print(*answers)

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

최초 풀이시 이동 경로를 모두 저장하였는데 최단거리의 경로가 한개가 아닌 여러개인 경우, 문제가 발생하였습니다.

경로를 모두 저장하였을때, 메모리 초과 문제가 발생하였습니다.

 

이후 메모리 문제 해결을 위하여 경로를 모두 저장하지 않았고, '출발지 -> g -> h -> 목적지' 또는 '출발지 -> h -> g -> 목적지' 의 거리를 부분별로 나누어서 각자 구하였습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

9370번: 미확인 도착지

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다