새로운 블로그로 이전 작업을 진행하고 있어 포스트가 새로 작성되고 있지 않습니다.

빠른 시일 내에 새로운 블로그로 인사드리겠습니다.

새로운 블로그 : https://unho.vercel.app/

본문 바로가기
알고리즘 문제풀이/Python

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

by 언호 2022. 7. 30.

📖 문제


🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

특정 출발점에서 목적지까지 도착하는 최단 경로를 구하기 위하여 다익스트라를 이용하였습니다.

또한, 거리 기록을 최초에 임의의 큰 값을 입력하여 도착 가능한 최단 경로를 구하도록 구성하였습니다.

 

두 지점의 노드를 필수적으로 통과해야 했으므로 '출발지 -> 노드1 -> 노드2 -> 도착지' 또는 '출발지 -> 노드2 -> 노드1 -> 도착지' 의 두가지 경우를 탐색하였습니다.

출발지, 노드1, 노드2 를 시작으로 하는 다익스트라를 세번 이용하였습니다.

2) 알고리즘

  • 다익스트라

3) 풀이 코드

사용 언어 - Python

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

def solution(start: int):                           # 다익스트라 탐색
    distance = [1e10] * (N+1)                       # 출발지로부터 각 노드까지 거리
    heap = [(0, start)]                             # 최소힙 리스트, 출발점 세팅
    
    while heap:
        dist, node = heapq.heappop(heap)
        if distance[node] > dist:                   # 아직 안가본 길이면, 거기까지 가는 최소 거리 저장
            distance[node] = dist
            for next in linked[node]:
                heapq.heappush(heap, (distance[node] + next[0], next[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번 정점에서 각 정점으로의 거리 구함

dis_1 = solution(necessary[0])                              # 꼭 방문할 첫번째 정점에서 다른 정점으로의 거리
dis_2 = solution(necessary[1])                              # 두번쨰 정점에서 다른 정점으로의 거리

# 출발지 -> n1 -> n2 -> 도착지와 출발지 -> n2 -> n1 -> 도착지 중 짧은 거리
ans = min(dis_init[necessary[0]] + dis_1[necessary[1]] + dis_2[N], dis_init[necessary[1]] + dis_2[necessary[0]] + dis_1[N])

# 경로 존재하지 않는다면 -1, 그 외 출력
if ans >= 1e10:
    print(-1)
else:
    print(ans)

🔗 문제 링크

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

 

1504번: 특정한 최단 경로

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존

www.acmicpc.net

 

 

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

'알고리즘 문제풀이 > Python' 카테고리의 다른 글

[백준] 1700 멀티탭 스케줄링  (0) 2022.08.16
[백준] 2206 벽 부수고 이동하기  (0) 2022.08.15
[백준] 1719 택배  (0) 2022.07.18
[백준] 6087 레이저 통신  (0) 2022.07.17
[백준] 15961 회전 초밥  (0) 2022.07.16

댓글