[백준1238] 파티

www.acmicpc.net/problem/1238

1238번: 파티

import heapq,sys
input = sys.stdin.readline

N,M,X = map(int,input().split())
INF = 987654321
graph = [[] for i in range(N+1)]


for _ in range(M):
    s,e,w = map(int,input().split())
    graph[s].append([w,e])


def f(graph,S,X): #출발지에서 목적지까지 최단시간 구하는 함수
    dist = [INF for i in range(M+1)]
    dist[S] = 0
    pq=[[0,S]]

    while pq:
        w,s = heapq.heappop(pq)

        if s == X:
            return w
        dist[s] = w
        

        for nw,nn in graph[s]:
            if dist[nn] != INF:
                continue
            heapq.heappush(pq,[w+nw,nn])

def f_X_to_home(graph,X):
    dist = [INF for i in range(N+1)]
    pq=[[0,X]]

    while pq:
        
        w,s = heapq.heappop(pq)

        if dist[s] != INF:
            continue

        dist[s] = w

        
        for nw,nn in graph[s]:
            if dist[nn] != INF:
                continue
            heapq.heappush(pq,[w+nw,nn])
    
    return dist


x_to_home = f_X_to_home(graph,X)

for i in range(1,N+1):
    if i == X:
        continue
    x_to_home[i]+=f(graph,i,X)

print(max(x_to_home[1:]))

풀이1 (안 좋은 풀이)

문제에서 시키는대로 모든지점 -> X 지점으로 가는 최단거리를 구하고

X -> 모든지점으로 가는 최단거리 구해서 더해준 다음에 최댓값을 찾았다.

최단거리는 다익스트라를 통해 구했다.

 

다익스트라는 어떤 지점에서 나머지 지점으로 가는 최단거리를 모두 구할 수 있고

N이 정점의 수 E가 간선의 수라고 했을 때 E*Log(N)의 시간복잡도를 가진다.

 

하지만 내가 한 풀이대로 풀면

E*Log(N) 를 N번 하기 떄문에 약 O(E*N*Log(N)) 이다.

 

문제가 풀리긴 하지만 효율이 안 좋다.

 

import heapq,sys
input = sys.stdin.readline

N,M,X = map(int,input().split())
INF = 987654321
graph = [[] for i in range(N+1)]
graph_reverse = [[] for i in range(N+1)]

for _ in range(M):
    s,e,w = map(int,input().split())
    graph[s].append([w,e])
    graph_reverse[e].append([w,s])

def dijkstra(graph,X):
    dist = [INF for i in range(N+1)]
    pq=[[0,X]]

    while pq:
        w,s = heapq.heappop(pq)

        if dist[s] != INF:
            continue

        dist[s] = w

        for nw,nn in graph[s]:
            if dist[nn] != INF:
                continue
            heapq.heappush(pq,[w+nw,nn])
    
    return dist

dist = dijkstra(graph,X)
dist_rev = dijkstra(graph_reverse,X)
answer = 0
for i in range(1,N+1):
    s = dist[i] + dist_rev[i]
    answer = max(s,answer)
print(answer)

 풀이2

다익스트라는 시작노드부터 나머지 노드까지 최단거리를 구한다고 하였다.

dijkstra(graph,X)는 인접그래프 형식의 graph를 통해 시작지점 X에서 나머지 지점들까지의 거리를 보여주는 dist 리스트를 반환한다.

 

그렇다면 A->B, B->C 이런식의 단방향 경로들을 모두 거꾸로 만든 graph_reverse를 만들고

dijkstra(graph_reverse,X) 를 하면 결과는 어떤 의미를 가질까?

 

어쨋든 다익스트라기 때문에 방향이 뒤집힌 그래프를 사용해 X에서 나머지 A,B,C 노드로 가는 최단거리가 구해진다.

하지만 실제로는 경로가 뒤집혔기 정상 그래프의 A->X, B->X, C->X, 즉 나머지 노드에서 X로가는 최단거리가 구해진다.

즉 다익스트라를 총 2번만 사용해서 답을 구할 수 있다.

 

시간복잡도는 그래서 O(E*Log(N)) 이다.