[프로그래머스] 가장 먼 노드 - 배열 원소 개수 세기

https://school.programmers.co.kr/learn/courses/30/lessons/49189

간단히 설명하면, 1번 노드로부터 가장 멀리 떨어진 노드의 개수를 구하는 문제이다.
dijkstra 알고리즘을 활용하면 특정 노드로부터 다른 모든 노드까지의 거리를 구할 수 있으므로 쉽게 풀 수 있다.

import heapq
INF = int(1e9)

def solution(n, edge):
    graph = [[] for _ in range(n+1)]
    for i in range(len(edge)):
        a, b = edge[i][0], edge[i][1]
        # 양방향 연결
        graph[a].append([b, 1])
        graph[b].append([a, 1])
    distance = [INF] * (n+1)        
    distance[0] = 0
    
    dijkstra(graph, 1, distance)
    
    return distance.count(max(distance))

def dijkstra(graph, start_node, distance):
    q = []
    distance[start_node] = 0
    heapq.heappush(q, (distance[start_node], start_node))
    
    while q:
        dist, now = heapq.heappop(q)
        
        for next_node, next_cost in graph[now]:
            cost = dist + next_cost
            
            if cost < distance[next_node]:
                distance[next_node] = cost
                heapq.heappush(q, (cost, next_node))

list.count(특정값)

해당 문법은 파이썬 리스트에서 특정값이 포함된 개수를 알 수 있게 해준다.
문자열에도 똑같이 적용됨!

물론 Counter 객체를 사용할 수도 있다.

from collections import Counter

cnt = Counter('Abracadabra!')

print(cnt)					# Counter({'a': 4, 'b': 2, 'r': 2, 'A': 1, 'c': 1, 'd': 1, '!': 1})
print(cnt['a'])				# 4
print(cnt.most_common(2))	# [('a', 4), ('b', 2)]