문제
풀이
일명 '그래프' 문제라고 불린다. 주어진 문제의 제시처럼 그래프를 만든 후 '1'번 노드부터 시작해서 다음 노드들을 방문할 때 가중치의 합이 K를 넘지않는 노드의 개수를 찾는 문제다.
시작 노드가 1이기 때문에 1에서 출발을 할 수 있도록 하며, 연결이 되어 있지 않을 수도 있고 노드 '1'에서 다음 노드로 갈 수 있는 노드의 가중치가 K보다 클 수도 있으므로 default 값, 즉 '1'마을은 배달을 할 수 있기에 기본 default 값으로 1을 설정한다.
노드(마을) a에서 b로 갈 때 가중치는 c 로 구성할 그래프를 생성하고, 거리를 담을 수 있는 리스트를 만드는데 그 리스트의 인덱스가 해당 마을 도착 거리가 된다. 해당 노드까지 도착할 수 있는 경우의 수는 여러가지이기에 가장 작은 값을 담을 수 있도록 한다.
풀이 순서를 보면,
코드
def solution(N, road, K):
answer = 1 # 자신의 마을은 배달을 무조건 할 수 있기에, default값은 1로 설정.
graph = [[] for _ in range(N + 1)]
for a, b, c in road: # 문제와 같이 양방향 그래프 생성
graph[a].append([b, c])
graph[b].append([a, c])
dist = [1e9] * (N + 1)
tree = []
tree.append([1, 0]) # 출발 노드
dist[1] = 0
while tree:
n, ncost = tree.pop()
for nv, cost in graph[n]:
if cost + ncost < dist[nv]: # 중복하여 tree에 담지 않도록 기존의 값보다 작은 값을 가질 때만 업데이트 하도록
dist[nv] = cost + ncost
tree.append([nv, dist[nv]])
for i in dist: # K보다 작거나 같은 값만 수를 센다. 그리고 dist[1], 즉 시작 노드의 값은 0이므로 이미 수를 세었기에 빼도록.
if 0 < i <= K:
answer += 1