<aside> 🔥 이코테 3번 문제

</aside>

<aside> 🔥 문제 정리

첫째줄에 도시개수 n, 통로 개수 m, 시작점 c 가주어진다.

다음 m개의 줄에 시작 도시 x, 도착 도시 y, 비용 z가 주어진다.

c 도시에서 다른 모든도시로 메세지를 보내려고 할 때,

메세지를 받을 수 있는 도시는 몇개이고, 최대 비용은 얼마나 드는가를 출력하는 문제이다.

</aside>

<aside> 🔥 접근 방법

이 문제는 시작점에서 각 노드로 가는 최단거리를 찾으면 해결할 수 있을 것 같다.

플로이드 워셜보다는 다익스트라로 구현하는게 맞는거 같다.

</aside>

<aside> 🔥 코드 진행

• 전체코드

입력값들을 받고 x, y, z로 그래프를 연결해준다. 그리고 다익스트르 알고리즘을 호출한다.

n, m, c = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    x, y, z = map(int, input().split())
    graph[x].append((y, z))

print(dijkstra(graph, c))

다음부터는 기본적인 힙을 이용한 다익스트라 알고리즘을 활용했다.

먼저 거리 테이블과 힙을 생성해서 힙에 (비용, 시작점)을 넣어 준다.

def dijkstra(graph, start):
    N = len(graph)

    # 거리 테이블 무한대로 초기화
    dist = [INF] * N

    # 힙 생성하여 (거리, 시작점) 넣기
    q = []
    heapq.heappush(q, (0, start))

    # 시작점은 거리비용 0부터 시작
    dist[start] = 0

힙에 값이 있는동안 반복하며 힙에서 가장 비용이 작은 노드 정보를 가져온다.

while q:
        # 힙에서 가장 비용이 적은 노드 정보 가져온다.
        acc, cur = heapq.heappop(q)

다음으로 이미 기록된게 더 비용이 적다면 건너뛰어준다. 어차피 답에 추가될 일 없기 때문이다.

# 이미 기록된게 현재 꺼내온 노드의 값보다 적다면 건너뛰기
if dist[cur] < acc:
    continue

현재 꺼낸 노드의 인접 노드와 그 인접노드의 비용을 가져온다.

이전 합계에 인접노드 비용을 더해 누적 합계를 계산하고 누적 합계가 기록된 것 보다 더 짧을 경우에는

업데이트를 해주고 힙에 넣어 다시 반복문을 돈다.

# 현재 꺼낸 노드의 그래프에서 인접 노드와 비용 정보 가져오기
for adj, d in graph[cur]:
    # 누적 합계 계산
    cost = acc + d

    # 인접노드로 거쳐온 비용이 더 짧은 경우
    if cost < dist[adj]:
        # 업데이트
        dist[adj] = cost
        heapq.heappush(q, (cost, adj))

마지막으로 정답처리를 해준다.

도시의 시작 개수를 -1로 잡아준 이유는 시작 노드는 제외해야하기 떄문이다.

만약 거리 테이블에서 무한대로 입력된 값이 있으면 메세지가 도달할 수 없기 때문에 카운트하지 않는다.

# 도시의 개수는 시작 노드는 제외.
    city_recieve_count = -1
    # 최대 거리 찾기
    max_cost = max(dist[1:])
    # 거리테이블에서 무한인 경우에는 도달할 수 없으므로 카운트 x
    for i in dist[1:]:
        if i != INF:
            city_recieve_count += 1
    print(dist)
    return city_recieve_count, max_cost

</aside>