[BOJ-1238] 파티

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

1238번: 파티

---

[풀이]

전형적인 최단경로 알고리즘의 다익스트라(Dijkstra)를 활용하는 문제이다.

다익스트라의 개념을 이해하면 쉽게 풀 수 있는 문제이다.

굳이 BFS, DFS, 플로이드 와샬을 안해도 풀 수 있다.

 

 

문제의 조건은 집에서 파티장으로 갈때 걸리는 시간과 파티장에서 집으로 돌아올때 걸리는 시간의 합이

최댓값을 구해야한다. 그러면 두가지의 경우를 나눠서 다익스트라를 해야한다.

(1) 집->파티장  걸린시간

(2) 파티장-> 집 걸린시간

 

(2)파티장-> 집의 경우에는 출발점이 X로 동일하다

그런데 (1) 집->파티장의 경우에는 출발점이 다르므로 N번의 다익스트라를 실행해야한다.

그러면 시간초과로 에러가 발생한다.

이를 해결하기 위해서는 파티장소(X)를 출발점으로 하여 도착점이 집으로 도달하게끔해야한다.

기존의 weight 를 바꿔야한다.

 

예를 들어서

weight(가중치) 초기값이 weight[2][1]=4, weight[1][2]=5 였다면

weight[2][1]=5, weight[1][2]=4 로 바꿔야하고

 

weight[3][5]=무한대, weight[5][3]=1 이라면,

weight[3][5]=1, weight[5][3]=무한대 식으로 바꿔야한다.

 

 

푼방법을 요약하자면 아래와같다.

(1) 파티장 -> 집 으로 도달할 때의 최단경로를 구한다. (초기 weight값 가지고 한다.)

(2) weight값을 변경한다.

(3) 집-> 파티장으로 도달할 때 최단경로를 구한다 (방향을 변경시킨 weight값 가지고한다.)

 

---

[코드]

import sys
from copy import deepcopy
input=sys.stdin.readline

# N: 학생수/  M: 도로개수 / X: 파티장소
N, M, X = map(int, input().strip().split())

# 가중치 집합 초기화
weight=[ [float('inf') if i!=j else 0 for j in range(N+1)] for i in range(N+1)]
for _ in range(M):
    start, end, time= map(int, input().strip().split())
    weight[start][end]=time

visited=None
distance=None

def choose():
    global distance, N, visited
    min_val= float('inf')
    min_pos=0
    for i in range(1,N+1):
        if (min_val> distance[i]) and (not visited[i]):
            min_val=distance[i]
            min_pos=i
    return min_pos
      

# 최단거리를 구한다.
def shortest_path(start): #start:시작정점, n: 정점개수
    global N,X, visited, weight, distance
    #초기화
    visited=[False]*(N+1)
    distance= deepcopy(weight[start]) #시작정점에 해당하는 가중치 복사.
    visited[start]=True #시작정점 방문표시

    #시작정점과 연결된 노드중 가장 짧은 거리를 갖는 노드(u)를 찾는다.
    #시작정점을 제외한 나머지 노드를 탐색해야하므로 최대 N-1회 반복한다. 
    for i in range(N-1):
        u=choose()
        visited[u]=True #연결노드 방문
        for w in range(1,N+1):
            if not visited[w]: #노드 w가 아직 방문하지 않은 상태라면
                if (distance[u]+weight[u][w]<distance[w]):
                    distance[w]=distance[u]+weight[u][w]
    

def main():
    global X,N, distance, visited, weight
    # cost_time: 각 학생이 파티장소까지 이동하고, 집으로 돌아오는데 걸린시간
    cost_time={}
    cost_time[X]=0

    #파티장->각 학생의 집
    shortest_path(X)
    for i in range(1,N+1):
        if i!=X:
            cost_time[i]=distance[i]

    #학생집-> 파티장
    #학생집을 출발점으로 하게되면 n번의 반복을 할 수있지만
    #방향만 바꿔준다면, 반복을 안해도 된다.
    # 즉, 파티장소(X)를 출발점으로해서 학생의 집에 도달할 수 있다.
    #weight[1][2]=4 , weight[2][1]=1 을 swapping
    visited= [[False]*(N+1) for _ in range(N+1)]
    for y in range(1,(N+1)):
        for x in range(1,(N+1)):
            if (not visited[y][x]):
                visited[y][x]=True
                visited[x][y]=True
                weight[y][x], weight[x][y]= weight[x][y], weight[y][x] 
    
    shortest_path(X)
    for i in range(1,N+1):
        if i!=X:
            cost_time[i]+=distance[i]
    print(max(cost_time.values()))

if __name__=='__main__':
    main()