알고리즘 - [프로그래머스] 가장 먼 노드 (Python)

2021년 7월 18일 글

문제

문제 설명

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

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

제한사항

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

풀이 아이디어

1) 1번 노드에서 가장 먼 노드?

• BFS로 한 층씩 내려가면서 찾아보자!

2) 그래프를 어떻게 구성할 것인가?

• 리스트 형태의 dict(defaultdict(list))? 또는 2차원 배열?
• 공간 절약을 위해 dict을 이용해보자!

3) 노드의 갯수를 어떻게 찾을 것이냐?

• while문으로 한 번 더 감싸서 각 층의 Queue의 길이를 이용하자!

코드

from collections import defaultdict, deque

def solution(n, edges):
    # 그래프 구성
    graph = defaultdict(list)
    for edge in edges:
        graph[edge[0]].append(edge[1])
        graph[edge[1]].append(edge[0])
        # 결과 : defaultdict(<class 'list'>, {3: [6, 4, 2, 1], 6: [3], 4: [3, 2], 2: [3, 1, 4, 5], 1: [3, 2], 5: [2]})

    def bfs(node, n):
        Q = deque()
        Q.append(1)
        visit = [False]*(n+1)   # 0번 인덱스부터 시작하므로
        visit[1] = True
        while Q:       
            Q_len = len(Q)
            answer = Q_len      
            while Q_len != 0:       # Q의 크기만큼 반복해줌으로써 깊이마다의 노드 갯수를 알 수 있음
                Q_len -= 1
                v = Q.popleft()     # Queue
                for next_node in graph[v]:
                    if not visit[next_node]:
                        Q.append(next_node)
                        visit[next_node] = True
        return answer

    return bfs(1,n)