[python3] 백준 1238 풀이 ( 파티, 다익스트라 )

[python3] 백준 1238 풀이 ( 파티, 다익스트라 )

이번 문제는 참신했다. 물론 내가 생각도 못해서 참신하게 느껴진거 겠지만ㅋㅋ

우선 문제를 보자

문제를 읽어보면 여러 곳에서 학생들이 X마을로 모인다. 이후에 각자 집으로 돌아갈 때 가장 오래 걸리는 학생의 소요 시간을 출력한다.

간단히 생각해보면 파티에 참석하는 경우 마을이 N개 이기 때문에 N -> X로 가는 경우의 수가 나올것이다.

파티가 끝나고 집에 가는 경우는 X -> N으로 가는 경우의 수가 나온다.

그럼 단순하게 보면 단일 시작점 알고리즘이 적용되면 안 되는거 같다. 왜냐하면 출발할 때 N개의 마을에서 각자 출발하기 때문이다. 그래서 나도 플로이드-워샬을 적용하고 풀고자 했다.

N=1000 이므로 N^3 = 1,000,000,000 = 10억, 21억 넘지 않아서 괜찮을 줄 알았다. (찾아보니 1초에 컴퓨터는 1억연산이 가능하다고 한다. 즉 안된다는 소리다.)

당연하게도 플로이드 워샬을 사용한 코드는 시간초과를 뱉어냈다.

그럼 다시 생각해보자. 가능한 방법은 다익스트라나 벨만-포드 같은 경우가 남는다.

우리는 다익스트라를 사용할때 주로 out degree로 인접 리스트(adj)를 나타낸다. (out degree는 해당 노드에서 향하는 차수를 의미한다. )즉, X->N은 단일 시작점 알고리즘이기 때문에 다익스트라로 구할 수 있다.

파티가 시작될때의 경로는 N->X 이다. 출발점이 단일 시작점이 아니기 때문에 다익스트라를 사용할 수 없다.

그럼 거꾸로 생각해보자.

만약 X에서 시작하더라도 자신한테 오는 가장 가까운 in degree부터 추가하는 형식으로 다익스트라를 진행한다면??

그러면 X가 도착점 이더라도 출발점 N에서 X까지의 최솟값을 구할 수 있다.

그럼 결과적으로 다익스트라를 단 2번만 하면 N -> X -> N을 구할 수 있다!!

그럼 끝이다 바로 코딩을 진행하면 된다.

1. out degree형태로 o_adj 배열 구하기

2. in degree형태로 i_adj 배열 구하기

3. 다익스트라(o_adj), 다익스트라(i_adj) 하기

4. 결과를 더하고 가장 큰 값 출력하기

""" N -> X -> N 원래 다익스트라는 outdegree기준으로 구함. 만약 indegree 기준으로 구한다면? N->X의 값을 구할 수 있다. 그럼 다익스트라 2번하면 N->X->N을 구할수 있다. """ import sys input = sys.stdin.readline N,M,X = map(int, input().split()) INF = 1000000000 i_adj = [ []for i in range(N+1) ] o_adj = [ []for i in range(N+1) ] for _ in range(M): a,b,c = map(int, input().split()) i_adj[b].append((a,c)) o_adj[a].append((b,c)) import heapq def daik(pq, adj): dp = [INF for i in range(N+1)] dp[X] = 0 while pq: cost, node = heapq.heappop(pq) if dp[node] < cost: continue for i in range(len(adj[node])): end, endcost = adj[node][i] if dp[end] > endcost + cost: dp[end] = endcost+cost heapq.heappush(pq, (dp[end],end)) return dp N_X = daik([(0,X)], i_adj) X_N = daik([(0,X)], o_adj) big = 0 for i in range(1, N+1): big = max(N_X[i] + X_N[i],big) print(big)

from http://guccin.tistory.com/132 by ccl(A) rewrite - 2021-08-28 22:00:41