[백준] 1238번 파티(python)

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

1238번: 파티

 

1. 난이도 골드3 (🥇)

 

2. 문제 해결 방법

우선 이 문제는 다익스트라로 풀면 되며, 학생은 n개로 구분된 마을에 한 명씩 살고있다는 조건이 있다.

 

예시를 보면 마을은 1,2,3,4,5번 5개가 있고, 파티의 장소는 2번이다.

 

따라서 아래와 같이 파티로 가는 길과 파티를 끝내고 집으로 돌아가는 길을 각각 다익스트라로 돌린 후

1,2,3,4,5번 중 가장 오래 걸린 값을 max 함수로 구해서 출력하면 된다.

 

1번->2번(파티로 가는 길)

2번 -> 1번(파티에서 집으로 돌아가는 길)

 

result = 0

for i in range(1,n+1):
  result = max(result, dij(i,x)+dij(x,i))
  
  #dij(i,x) = 파티로 가는 길
  #dij(x,i) = 파티가 끝나고 집으로 가는길

 

3. 내가 작성한 코드

import heapq
INF = int(1e9)
n,m,x = map(int,input().split()) #n학생 m도로 x도착

graph = [[] for _ in range(n+1)]
for i in range(m):
  a,b,c = map(int,input().split()) #a시작 b끝 c가중치
  graph[a].append((b,c))

def dij(start,end):
  dist = [INF] * (n+1)
  q = []
  heapq.heappush(q,(0,start))
  dist[start] = 0

  while q:

    x, now = heapq.heappop(q)

    if dist[now] < x:
      continue

    for i in graph[now]:
      cost = x + i[1]
      if dist[i[0]] > cost:
        dist[i[0]] = cost
        heapq.heappush(q,(cost,i[0])) 
    
  return dist[end]

result = 0

for i in range(1,n+1):
  result = max(result, dij(i,x)+dij(x,i))

print(result)

 

4. 메모

학생들이 각 마을에 살고있다는 조건을 읽지 않고 풀어서 대혼란이었다.

 

가중치가 제일 큰 값부터 선택할 수 있게 최대힙도 이용해보고,, 별 짓 다했는데

 

다시 보니까 내가 문제를 제대로 읽지 않은 것이었음ㅠ

 

문제 좀 잘 읽고 풀자,,,,

 

참고로 이 문제를 플로이드로 풀을 수도 있을 것 같은데 그러기에는

 

input값이 크고, 플로이드 알고리즘의 시간복잡도가 높아서(O(N^3))시간초과가 발생한다.