[백준][Python] 1238 파티 : 역방향 그래프로 돌아오는 길을 찾자

[백준][Python] 1238 파티 : 역방향 그래프로 돌아오는 길을 찾자

처음 풀이는 다음과 같다. 모든 노드에 갔다가 돌아오는 각 합중 max값을 찾는 풀이

그리고 다른 분들의 풀이를 본 결과 역방향 그래프를 그리는 것이 반대로 도착지점에서 현지점까지 오는 거리를 측정할 수 있음을 깨달았다.

import sys input = sys.stdin.readline from heapq import heappop, heappush def dijkstra(start): heap = [] visited = {i: float('inf') for i in range(1, N + 1)} visited[start] = 0 heappush(heap, (0, start)) while heap: time, cur_node = heappop(heap) if visited[cur_node] < time: continue for next_node, next_time in graph[cur_node]: if visited[next_node] > time + next_time: visited[next_node] = time + next_time heappush(heap, (visited[next_node], next_node)) return visited N, M, X = map(int, input().split()) graph = {i: [] for i in range(1, N + 1)} for __ in range(M): s, e, t = map(int, input().split()) graph[s].append((e, t)) max_dist = 0 dist_X = dijkstra(X) for i in range(1, N + 1): if i == X: continue each = dijkstra(i) max_dist = max(max_dist, dist_X[i] + each[X]) print(max_dist)

다른분의 풀이(역방향 그래프 이용)

import sys from heapq import heappush, heappop input = sys.stdin.readline n, m, x = map(int, input().split()) inf = 100000000 s = [[] for i in range(n + 1)] dp = [inf] * (n + 1) s_r = [[] for i in range(n + 1)] dp_r = [inf] * (n + 1) def dijkstra(start, dp, s): heap = [] dp[start] = 0 heappush(heap, [0, start]) while heap: w, n = heappop(heap) if dp[n] < w: continue for n_n, wei in s[n]: n_w = wei + w if n_w < dp[n_n]: dp[n_n] = n_w heappush(heap, [n_w, n_n]) for i in range(m): a, b, t = map(int, input().split()) s[a].append([b, t]) s_r[b].append([a, t]) dijkstra(x, dp, s) dijkstra(x, dp_r, s_r) max_ = 0 for i in range(1, n + 1): max_ = max(max_, dp[i] + dp_r[i]) print(max_)

정방향을 통해 X -> 특정노드

역방향을 통해 X -> 특정노드의 역 방향 즉 특정노드 -> X까지 오는 경로를 역으로 타고 들어간다.

from http://devlibrary00108.tistory.com/537 by ccl(A) rewrite - 2021-09-30 02:00:45