[백준] 1504 특정한 최단 경로

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

초기에 도착지점에 도착했을때, 필수로 방문해야하는 정점을 방문했는지 확인이 필요하여 최소힙을 사용하는 과정에서 방문한 정점의 리스트의 정보를 같이 최소힙에 저장을 시키는 방식으로 접근했습니다.

그러나 최소힙에 경로를 저장하는 리스트를 같이 할당하여 반복시켰기 때문에 메모리 초과가 발생했습니다.

 

이 문제를 해결하기 위해 정점 방문 기록을 삭제하고, 다익스트라를 최초 1번 정점, 필수 방문해야하는 정점 2개를 탐색하도록 접근하였습니다.

2) 알고리즘

• 다익스트라

3) 풀이 코드

사용 언어 - Python

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


def solution(start: int):                           # 다익스트라 탐색
    distance = [-1] * (N+1)                         # 출발지로부터 각 노드까지 거리
    heap = [(0, start)]                             # 최소힙 리스트, 출발점 세팅

    while heap:
        node = heapq.heappop(heap)
        if distance[node[1]] < 0:                   # 아직 안가본 길이면, 거기까지 가는 최소 거리 저장
            distance[node[1]] = node[0]
            for e in linked[node[1]]:
                heapq.heappush(heap, (distance[node[1]] + e[0], e[1]))
    return distance


N, E = map(int, sys.stdin.readline().split())           # 정점의 개수, 간선의 개수
linked = [[] for _ in range(N+1)]                       # 정점들 간에 연결 관계

for _ in range(E):
    a, b, c = map(int, sys.stdin.readline().split())    # 출발 정점, 도착 정점, 두 정점간 거리
    linked[a].append((c, b))                            # 정점 양방향 연결 관계 설정
    linked[b].append((c, a))

necessary = list(map(int, sys.stdin.readline().split()))    # 꼭 방문해야할 정점 리스트

dis_init = solution(1)                      # 1번 정점에서 각 정점으로의 거리 구함

if dis_init[necessary[0]] >= 0 and dis_init[necessary[1]] >= 0:     # 꼭 방문해야하는 두 정점을 갈 수 있다면
    dis_1 = solution(necessary[0])          # 꼭 방문할 첫번째 정점에서 다른 정점으로의 거리
    dis_2 = solution(necessary[1])          # 두번쨰 정점에서 다른 정점으로의 거리

    # 1 -> 정점1 -> 정점2 -> N 과 1 -> 정점2 -> 정점1 -> N 으로 가는 두가지 방법 중 더 짧은 거리 출력
    print(min(dis_init[necessary[0]] + dis_1[necessary[1]] + dis_2[N], dis_init[necessary[1]] + dis_2[necessary[0]] + dis_1[N]))
else:
    print(-1)

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

두 정점을 무조건 들러야하는데, 방문한 기록을 리스트를 이용하여 기록하였으나 메모리를 줄이는 방법에 어려움을 겪었습니다.

(1) 참고 사이트

• 블로그
  1 -> 정점1 -> 정점2 -> N 과 1 -> 정점2 -> 정점1 -> N 2개의 경로에서 최소 거리를 선택하는 방법을 알게되었습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

1504번: 특정한 최단 경로

 

 

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