💻코딩테스트 문제풀이17

Chapter11. 자주 등장하는 자료 구조

[문제45] 가장 먼 노드 - Level3

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀 있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단 경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return하도록 solution 함수를 작성해주세요.

[제한사항]

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 {a, b}는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

[코드작성]

1. 그래프를 만들 배열과 각 노드별 누적 상황을 기록할 배열을 생성합니다.

def solution(n, edge):
	answer = 0
    route = [0] * (n+1)
    graph = [[] for i in range(n+1)]

2. 노드 데이터를 기반으로 그래프 만들기

for e in edge:
	graph [e[0]].append(e[1])
    graph [e[1].append(e[0])

3. 탐색 준비

from collections import deque

queue = deque()
queue.append(1)
route[1] = 1

4. BFS 탐색 수행

while queue:
	now = queue.popleft()
    for g in graph[now]:
    	if route[g] == 0:
        	queue.append(g)
            route[g] = route[now] + 1

5. 나온 노드 데이터 중 가장 먼 노드의 개수 파악

max_edge = max(route)

	for r in route:
    	if r == max_edge:
        	answer += 1

[전체코드]

from collections import deque

def solution(n, edge):
	answer = 0
    route = [0]*(n+1)
    graph = [[] for i in range(n+1)]
    queue = deque()
    
    for e in edge:
    	graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])
        
    queue.append(1)
    route[1] = 1
    
    while queue:
    	now = queue.popleft()
        for g in graph[now]:
        	if route[g] == 0:
            	queue.append(g)
                route[g] = route[now] + 1
                
    max_edge = max(route)
    
    for r in route:
    	if r == mox_edge:
        	answer += 1
            
    return answer