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

문제 링크: programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

 

 

문제 설명

1번 노드로부터 가장 멀리 떨어진 노드의 개수를 출력하는 문제입니다. 

1번 노드부터 BFS를 수행하며 1번 노드와의 distance를 저장한 뒤, distance가 가장 큰 값을 갖는 원소의 개수를 반환하도록 코드를 작성했습니다. 

 

1. 인접 노드 정보를 저장할 graph와 1번 노드로부터의 거리를 저장할 distance 초기화
2. 주어진 edge 정보를 graph에 저장
3. 1번 노드의 distance를 0으로 하고, 1번 노드를 큐에 삽입 (BFS 시작)
4. 큐에서 원소를 하나 꺼내고(v) 해당 원소에 방문하지 않은 인접 노드(x)가 있다면
   1) 해당 인접 노드(x)의 distance를 부모 노드(v)의 (distance + 1)로 갱신   // 방문처리를 포함
   2) 큐에 x 노드 삽입
5. 4번과정을 큐가 빌 때까지 반복 (BFS 수행)
6. BFS 수행이 끝나면 distance의 최댓값을 갖는 원소의 개수 반환

 

 

 

소스코드

from collections import deque

def bfs(start, graph, distance):
    distance[start] = 0
    queue = deque([start])
    
    while queue:
        v = queue.popleft()
        for x in graph[v]: # 방문하지 않은 인접 노드 방문
            if distance[x] == -1:
                # 현재 노드의 거리 = 부모 노드의 거리 + 1
                distance[x] = distance[v] + 1
                queue.append(x)

def solution(n, edge):
    answer = 0
    graph = [[] for _ in range(n + 1)]
    distance = [-1] * (n + 1)
    # 인접한 노드 정보를 graph에 저장
    for (v1, v2) in edge:
        graph[v1].append(v2)
        graph[v2].append(v1)

    bfs(1, graph, distance)
    answer = distance.count(max(distance))
    return answer