Python3
문제
제한사항
입출력
주요 포인트
데큐(deque)와 BFS를 활용한 문제이다.
변수 answer은 가장 멀리 떨어진 노드의 개수를 나타낸다.
route는 각 노드의 최단거리 리스트이다.
egde를 1부터 시작하게끔 오름차순으로 정렬한다.
데큐를 선언한다.
graph는 연결된 노드 정보를 나타낸다.
반복문 (edge만큼)
양방향 그래프를 만들기 위해 graph[i[0]]에 i[1]을 담고, graph[i[1]]에 i[0]을 담는다.
노드 1로부터 떨어진 거리를 묻는 문제이기 때문에 데큐의 출발 노드를 1로 설정한다.
출발노드의 최단거리는 1이다.
반복문 (큐에 원소가 있을 때까지)
현재 노드를 que.popleft()값으로 초기화한다.
이중 반복문 (양방향 그래프만큼)
현재 노드에서 이동할 수 있는 모든 노드를 확인한다.
만약 아직 방문하지 않은 노드이면(if route[next] == 0:),
- 데큐에 그 값을 추가한다. (que.append(next))
- 최단거리를 갱신한다. (route[next] = route[now] + 1)
반복문 (각 노드의 최단거리 리스트만큼)
가장 멀리 떨어진 노드 개수를 구하는 반복문이다.
만약 route리스트의 max값이 r과 같다면 answer에 1을 증가시킨다.
최종 answer를 리턴한다.
최종 코드
from collections import deque
def solution(n, edge):
answer = 0
route = [0] * (n+1)
edge.sort()
que = deque()
graph = [[] for i in range(n+1)]
# 양방향 만들기
for i in edge:
graph[i[0]].append(i[1])
graph[i[1]].append(i[0])
que.append(1)
route[1] = 1
while que:
# 현재 노드
now = que.popleft()
# 현재 노드에서 이동할 수 있는 모든 노드 확인하기
for next in graph[now]:
# 아직 방문하지 않은 노드면
if route[next] == 0:
que.append(next) # 큐에 추가
route[next] = route[now] + 1 # 최단거리 갱신
# 가장 멀리 떨어진 노드 개수 구하기
for r in route:
if r == max(route):
answer += 1
return answer피드백
처음 그래프 문제를 풀어 봤는데 어렵다. 내가 할 수 있을까 ,,
I mean