[BOJ] 1238번 파티 / 사용언어 : 파이썬(python)

※ 문제링크

1238번: 파티

※ 관련 개념

23. 다익스트라(Dijkstra) 알고리즘

 

해당문제는 가중치가 있는 단방향 그래프에서 최단거리를 구하는 것과 관련된 문제로 다익스트라 알고리즘을 활용하여 풀 수 있는 문제였다. 다익스트라 알고리즘에 대해 잘 설명해준 사이트를 참조사이트로 걸어놓았으니 개념이해가 필요한 사람들은 참고하면 좋을 거 같다. 다익스트라 알고리즘 구현을 위해서는 자료구조인 우선순위큐, 그래프, 가중치를 갱신할 리스트가 필요하다. 파이썬에서는 최소힙을 지원해주고 있어서 해당 내용을 활용하여 문제를 해결하였다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값들을 바탕으로 리스트를 활용하여 가중치를 포함한 그래프를 구현한다.

2. heapq를 활용하여 최소힙을 구현하고 출발점을 넣으면 그래프와 연동하여 각 정점으로 이동할 수 있는 최단시간을 도출할 다익스트라 알고리즘을 작성한다.

3. 1부터 n까지 다익스트라 알고리즘을 반복문을 돌려서 각 정점별로 왕복시간을 구한다음 최대값을 출력한다.

 

# 조건1: 모든 학생들은 X로 갈 수 있고, X에서 집으로 돌아올 수 있다.
from heapq import heappush, heappop
import sys

# input = sys.stdin.readline
N, M, X = map(int, input().split()) # N: 학생의 수 / M: 도로의 수 / X: 소요시간
graph = [[] for _ in range(N+1)] # 그래프 구현
for _ in range(M):
    s, e, t = map(int, input().split())
    graph[s].append([t, e])

def dijkstra(start):
    heap = []
    dp = [float('inf') for _ in range(N+1)] # 가중치 갱신을 위한 리스트
    heappush(heap, [0, start]) 
    dp[start] = 0

    while heap:
        t1, p1 = heappop(heap)
        for t2, p2 in graph[p1]:
            # X에서 p2로 가는 가중치보다 X에서 p1으로 이동하는 가중치가 크면 명령 미실행
            if t1 > dp[p2]: 
                continue
            t3 = t1 + t2
            # 기존 가중치보다 작은 값이 나오면 값을 대체하고 해당 가중치와 정점을 자료구조에 저장
            if t3 < dp[p2]: 
                dp[p2] = t3
                heappush(heap, [t3, p2]) 
    return dp

# 반복문을 활용한 최단시간 도출
time = [0 for _ in range(N+1)]
p_h = dijkstra(X)
for i in range(1, N+1):
    if i != X:
        cp1 = dijkstra(i)[X]
        time[i] += cp1 + p_h[i]
print(max(time))

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다