백준 - 1238번 파티 python 문제풀이 [Hellfer]

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

1238번: 파티

🔷 알고리즘 분류 - 그래프 이론, 데이스크트라, 최단경로

난이도 - 골드 3

다익스트라 알고리즘이란 특정한 시작 노드에서 출발하여 그래프 상의 모든 다른 노드로 가는 최단 경로를 찾는 알고리즘입니다. 

 

음의 간선이 없는 경우에만 사용할 수 있습니다.

다익스트라 알고리즘은 '탐욕적인 방법'을 사용합니다. 

 

매번 '가장 비용이 적게 드는 노드'를 선택해서 반복함으로써 최적의 해를 찾아냅니다.

이 알고리즘의 동작 과정은 다음과 같습니다:

1. 출발 노드를 설정합니다.

2. 최단 거리 테이블을 초기화합니다.

 

3. 초기에는 출발 노드를 제외한 모든 노드의 최단 거리를 무한으로 설정합니다.

4. 출발 노드를 기준으로 각 노드의 최단 거리를 계산합니다. 

 

그리고 그중에서 최단 거리를 가지는 노드를 선택합니다.

5. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다.

위 과정을 반복합니다.

다익스트라 알고리즘은 최단 거리를 저장하는 1차원 리스트를 이용하므로 메모리를 적게 사용하고, 간선의 비용을 비교하여 최단 거리를 갱신하므로 원리가 이해하기 쉽다는 장점이 있습니다.

다만, 모든 간선을 검사해야 하므로 그래프의 크기가 크거나 간선의 개수가 많은 경우에는 시간이 오래 걸릴 수 있습니다. 

 

이런 경우에는 더 효율적인 알고리즘인 플로이드-워셜 알고리즘이나 벨만-포드 알고리즘이 사용될 수 있습니다.

🔶문제 풀이 - 데이스크트라를 이용한 풀이

import sys
import heapq
input=sys.stdin.readline

INF=float('inf')

# 노드의 수(n), 간선의 수(m), 시작 노드(start) 입력 받기
n,m,start=map(int,input().split())
# 입력 받은 노드의 수 만큼 간선 정보를 담을 공간(graph)과 결과를 담을 공간(result) 생성
graph=[[] for _ in range(n+1)]
result=[[] for _ in range(n+1)]

# 간선의 수 만큼 간선 정보를 입력 받아 graph와 result에 저장
for _ in range(m):
    x,y,z=map(int,input().split())
    graph[x].append((y,z))  # x에서 y로 가는 비용 z
    result[y].append((x,z))  # y에서 x로 가는 비용 z
    
# 다익스트라 알고리즘 함수
def dijkstra(start,graph):
    # 시작 노드로부터의 거리를 저장할 리스트 생성, 초기 값은 무한대
    distance=[INF]*(n+1)
    queue=[]
    # 시작 노드의 거리는 0으로 설정
    distance[start]=0
    heapq.heappush(queue,(0,start))  # 우선순위 큐에 (거리, 노드) 정보 삽입
    while queue:
        a,b=heapq.heappop(queue)  # 거리가 가장 짧은 노드 정보 꺼내기
        if distance[b]<a:  # 이미 처리된 노드라면 무시
            continue
        for i in graph[b]:  # 해당 노드의 인접 노드들에 대해 거리 정보 갱신
            cost=a+i[1]
            if distance[i[0]]>cost:
                distance[i[0]]=cost
                heapq.heappush(queue,(cost,i[0]))  # 우선순위 큐에 갱신된 거리 정보 삽입
    return distance  # 최종 거리 정보 반환

# 시작 노드로부터의 거리 정보와, 시작 노드로의 거리 정보 계산
q=dijkstra(start,graph)
w=dijkstra(start,result)
# 가장 큰 왕복 거리 계산
max_distance=max([q[i]+w[i] for i in range(1,n+1)])

print(max_distance)  # 가장 큰 왕복 거리 출력

🔶문제 이해하기

아래와 같은 입력값이 주어졌다고 가정해 보겠습니다.

 

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

 

1. 간선 정보와 결과를 담을 리스트를 초기화합니다.

2. 간선 정보를 입력받아서 graph와 result에 저장합니다.

3. graph와 result는 다음과 같이 설정됩니다.

 

graph = [[], [(2, 4), (3, 2), (4, 7)], [(1, 1), (3, 5)], [(1, 2), (4, 4)], [(2, 3)], []]
result = [[], [(2, 1), (3, 2)], [(1, 4), (4, 3)], [(1, 2), (2, 5)], [(1, 7), (3, 4)], []]

 

4. 다익스트라 알고리즘을 시작 노드(2)로부터의 거리를 계산하여 q에, 시작 노드로의 거리를 계산하여 w에 저장합니다.

5. q와 w는 다음과 같이 계산됩니다.

 

q = [inf, 1, 0, 5, 7, inf]
w = [inf, 1, 0, 2, 3, inf]

 

6. max_distance는 다음과 같이 계산됩니다.

 

max_distance = 10  # (q[4] + w[4] = 7 + 3)

 

따라서 출력값은 아래와 같습니다.

 

10