[프로그래머스/Python] 가장 먼 노드 - Level3

[프로그래머스/Python] 가장 먼 노드 - Level3

728x90

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

이 문제는 최단거리를 찾는 문제로 BFS 로 풀 수 있었다. 전형적인 BFS 문제여서 기본적인 BFS 구조만 알고 있다면 쉽게 풀 수 있을 것이다. 최근에 BFS를 공부했어서 쉽게 풀 수 있었던 것 같다.

from collections import deque def solution(n, edge): answer = 0 graph = [[] for _ in range(n+1)] # 연결된 노드 정보 그래프 distance = [-1] * (n+1) # 각 노드의 최단거리 리스트 # 연결된 노드 정보 추가 for e in edge: graph[e[0]].append(e[1]) graph[e[1]].append(e[0]) queue = deque([1]) # BFS를 위한 큐, 출발 노드는 1 distance[1] = 0 # 출발 노드의 최단거리 0으로 # BFS 수행 while queue: now = queue.popleft() # 현재 노드 # 현재 노드에서 이동할 수 있는 모든 노드 확인 for i in graph[now]: if distance[i] == -1: # 아직 방문하지 않은 노드라면 queue.append(i) # 큐에 추가 distance[i] = distance[now] + 1 # 최단거리 갱신 # 가장 멀리 떨어진 노드 개수 구하기 for d in distance: if d == max(distance): answer += 1 return answer

1. 연결된 노드 정보 그래프(graph) 와 각 노드의 최단거리를 저장하는 리스트(distance) 생성 후 graph에 노드 연결 정보를 추가한다. 간선이 양방향이므로 양쪽으로 추가해줘야 한다.

2. BFS를 위한 큐(queue) 를 생성한다. 출발 노드는 1이므로 미리 출발 노드를 넣어둔다. 출발 노드의 최단거리는 0 으로 만든다.

3. BFS를 수행한다.

3-1. 현재 노드(now) 를 가져온다.

3-2. 현재 노드에서 이동할 수 있는 모든 노드를 확인한다. 아직 방문하지 않은 노드라면 queue에 추가하고 최단거리를 갱신한다.

4. 가장 멀리 떨어진 노드 개수를 구한다.

728x90

from http://soohyun6879.tistory.com/183 by ccl(A) rewrite - 2021-08-08 12:00:25