[백준] 17270. 연예인은 힘들어 (파이썬)

🗂️   문제 

17270. 연예인은 힘들어

---

---

📌   Point

Dijkstra

그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

• 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우에 사용한다.

 
특징

• 음(-)의 간선이 없을 때 정상적으로 동작
• ‘각 노드에 대한 현재까지의 최단 거리’ 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신

 
작동 방식

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 위 과정에서 3번과 4번을 반복한다.

 
 
 

---

📄   코드

import heapq   # 우선순위 큐 사용

INF = int(1e10)   # 무한으로 초기화

def main():
    V, M = map(int, input().split())
    graph = [[] for _ in range(V+1)]   # 인접 리스트 그래프 초기화
    for _ in range(M):
        a, b, c = map(int, input().split())   # a에서 b까지 거리 c
        graph[a].append((b, c))   # 양방향 그래프이기 때문에 a,b에 각각 append 해줘야 함
        graph[b].append((a, c))

    J, S = map(int, input().split())   # J: 지헌 출발점, S: 성하 출발점
    J_distance = [INF] * (V+1)   # 지헌의 최단 거리 배열
    S_distance = [INF] * (V+1)   # 성하의 최단 거리 배열

    # 다익스트라 구현
    def dijkstra(start, distance):
        q = []
        
        heapq.heappush(q, (0, start))
        distance[start] = 0
        while q:
            dist, now = heapq.heappop(q)
            if distance[now] < dist:
                continue
            for i in graph[now]:
                cost = dist + i[1]
                if cost < distance[i[0]]:
                    distance[i[0]] = cost
                    heapq.heappush(q, (cost, i[0]))
    
    

    # 지헌
    dijkstra(J, J_distance)   # 지헌의 위치를 기준으로 다익스트라 실행

    # 성하
    dijkstra(S, S_distance)   # 성하의 위치를 기준으로 다익스트라 실행

    place = -1   # 약속 장소 초기화
    min_distance_sum = INF   # 거리 합 최솟값

	# 약속 장소 정하기
    for i in range(1, V+1):
        if i != J and i != S:   # 지헌과 성하의 출발점은 제외
            if J_distance[i] + S_distance[i] < min_distance_sum:   # 약속 지점까지의 지헌, 성하 거리 합의 최솟값
                min_distance_sum = J_distance[i] + S_distance[i]
    
    min_j_dist = INF   # 지헌이 이동하는 거리
	
    # 번호가 가장 큰 것부터 확인하며 조건을 만족하는 경우가 여러 개라면 작은 번호의 지점 찾기
    for i in range(V, 0, -1):
        jd, sd = J_distance[i], S_distance[i]
        if i!= J and i != S:
            if jd <= sd and jd + sd == min_distance_sum:   # 지헌이 더 가깝거나 둘이 이동하는 거리가 같은 지점이며 거리 합이 최소인 경우
                if min_j_dist >= jd:   # 지헌이 이동하는 거리가 더 짧으면
                    place = i   # 약속 지점 갱신
                    min_j_dist = jd   # 지헌이 이동하는 거리 갱신

    print(place)

if __name__ == "__main__":
    main()

 
 
 

---

✍🏻   풀이

시간 복잡도 : O((V + M) log V)

 

1.  다익스트라 

변형 없이 기본 다익스트라 알고리즘을 그대로 구현한 후, 이를 활용한다.
 

• 지헌과 성하의 각 출발점을 기준으로 모든 지점까지의 최단 거리를 구한다. (J_distance, S_distance)
• dijkstra(J (or S), J_distance(or S_distance)) 로 입력받은 두 사람의 출발점을 start 값으로 넣어준 후 계산한다.

 

2.  거리 조건

이 문제는 조건을 주어진 대로 철저하게 구현을 해야 통과가 된다.
 

• 첫 번째 for문   :   두 사람의 약속 지점까지 거리의 합이 최소가 되는 지점을 찾는다.
  1. 문제 조건의 1, 2에 부합하는 지점을 찾고자 한다.
  2. 약속 지점은 지헌과 성하의 위치가 될 수 없으며 (i != J and i != S)
  3. 지헌이 걸리는 시간과 성하가 걸리는 시간의 합이 최소가 되는 지점이어야 한다. (min_distance_sum을 최소값으로 갱신)

 
첫 번째 for문에서 구한 min_distance_sum 값을 두 번째 for문의 조건으로 사용한다.
 

• 두 번째 for문   :   적절한 약속 지점을 탐색한다.
  • 문제 조건의 3, 4에 부합하는 지점을 찾고자 한다.
    
    1. 약속 지점은 지헌과 성하의 위치가 될 수 없으며 (i != J and i != S)
    2. 지헌이가 성하보다 더 가깝거나 같으면서(jd <= sd) & 두 사람이 각자 걸리는 시간의 합이 최솟값이면서
    3. 현재 약속장소보다 지헌이의 위치에서 더 가까운 지점이 있는 경우
    4. 해당 지점을 약속 장소로 정한다.
  • for문은 V ~ 0까지 높은 번호부터 확인하며 조건에 부합하는 지점이 여러 개인 경우 낮은 번호가 약속 장소로 정해질 수 있도록 한다.