[백준/1238] 파티 | 다익스트라 | 왕복 거리 계산 |

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

1238번: 파티

 

지금까지 풀었던 다익스트라 문제들에서 약간 응용된 부분이 있는 문제다.

다익스트라는 bfs, dfs처럼 원리를 통해 특정 경로, 비용 등을 계산하는 알고리즘이다.

따라서 이 원리에 대해서 잘 이해하고 어떻게 쓰는지 외우며 다양한 문제를 풀어보면 크게 어려울 것 없다.

 

일단 dfs, bfs를 공부할 때와 마찬가지로 어떤 원리를 가지고 있고, 이 원리를 코드로 어떻게 구현하는지에 대한 큰 틀을 잡았다.

다익스트라

1. 시작점이 주어진다.
2. 시작점을 출발지로 [INF] * (n+1)로 초기화된 node의 가중치 정보를 갱신하며 그래프 탐색을 한다.
3. 이때 노드들을 방문하면서 python heapq를 사용하여 노드 번호와 가중치를 체크하면 최단거리를 찾을 수 있다.
4. graph는 i번째 노드에서 j번째 가는 가중치(w)를 저장해야 하므로 이차원 리스트로 구현한다.

---

이정도 세팅을 하고 다익스트라 함수를 구현하면 된다. 다익스트라 알고리즘을 구현하는 함수는 다음과 같다.

def dijkstra(start):

# 시작 노드로 가기 위한 최단 경로는 0으로 설정 
    q = []
    heapq.heappush(q, (0, start))
    node[start] = 0
    
    while q:
    	# 최단 거리 노드에 대한 정보 꺼내기
        d, now = heapq.heappop(q)
        # 현재 노드가 이미 처리되었다면 무시
        if node[now] < d: continue
        
        # 현재 노드와 연결된 다른 인접 노드를 확인해서 
        for i in graph[now]:
            dst = i[0]
            cost = d+i[1]
            
            # 해당 인접 노드가 최단거리라면 그 값으로 갱신
            if cost < node[dst]:
                heapq.heappush(q, (cost, dst))
                node[dst] = cost

우선순위 큐를 통해 배열을 구현하였기 때문에 heappop을 하면 자동으로 min값이 도출된다.

이를 통해 가장 최단거리인 노드에 대한 정보를 꺼낼 수 있다.  d: cost, now: node

 

만약 heaqp에서 꺼낸 노드가 이미 처리된 값이라면 무시를 하고, 다른 인접노드를 확인하여 이 값들을 비교해 최단 거리를 구한다.

---

문제 해결 

이렇게 하면 다익스트라 함수 실행을 통해 최단 거리를 바로 구할 수 있는데 1238 문제에서는 추가로 고려해야 할 점이 있다.

 

1. n번의 마을에 사는 학생 1명이 x번 마을로 가는 최단 경로 값을 구해야한다. 즉, 1-2-3-4-...-n번 마을에 해당하는 학생이 x 마을에 가는 최단경로의 모든 값을 구해야한다.

2. n번 마을에서 x번 마을로 갔다가 돌아오는 왕복값을 계산해주어야 한다. 이때 도로가 단방향이므로 갈 때의 최단 경로와 돌아올 때의 최단 경로는 다르기 때문에 각각에 대해 구해야한다.

 

이를 구현하기 위해서 

1. 각각의 학생마다 다익스트라 함수를 실행하여 최단경로 값을 구해준다. 이를 위해 조심해야 할 점이 있다. 원래 node의 초기값은 다익스트라 함수 외부에서 선언을 해주었지만 다익스트라 함수 내부에서 선언하여 n번의 학생 마다 선언해주어야 한다.

2. 다익스트라 함수를 각각의 학생마다 실행하기 위해서 for문으로 시작점을 날린다. 

---

전체 코드

import sys; input=sys.stdin.readline
import heapq

def dijkstra(start, end):
    q = []
    # 각자의 집에서 하나하나 구하는 것이므로 node를 함수가 실행될 때 마다 초기화
    node = [INF] * (n+1)
    heapq.heappush(q, (0, start))
    node[start] = 0
    
    while q:
        d, now = heapq.heappop(q)
        if node[now] < d: continue
        
        for i in graph[now]:
            dst = i[0]
            cost = d+i[1]
            
            if cost < node[dst]:
                heapq.heappush(q, (cost, dst))
                node[dst] = cost

    return node[end]

# main 
n,m,x = map(int, input().split())

graph = [[] for _ in range(n+1)]
INF = int(1e9)

for _ in range(m):
    i, j, w = map(int, input().split())
    graph[i].append((j, w))
    
t = 0
# 각자의 집에서 x 마을까지의 최단 경로 + x 마을에서 각자의 집까지의 최단 경로 
for i in range(1, n+1):
    if i == x : continue
    # 중에서 최댓값
    t = max(t, dijkstra(i,x)+dijkstra(x,i))

print(t)