[Programmers] 가장 먼 노드

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

문제 요약 및 해설

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

입력 정보는 노드의 개수(n)과 간선 정보(vertex), vertex[a][b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미이다.

* 문제 해결 방법

1. vertex로부터 그래프 자료구조를 표현한다. 인접행렬 또는 인접리스트 방식으로 만든다.

2. 1에서 만든 그래프를 1번 노드부터 그래프를 탐색하면서 각 노드마다 1번노드로 부터 최단 경로로 이동할때 지나온 간선의 개수를 구한다. 문제에서 주어진 그래프는 가중치가 없는 그래프이기 때문에 BFS탐색을 통해 최단 경로를 구한다.

3. 2번에서 구한 각 노드마다 최단경로로 이동 했을 때 간선의 개수를 저장한 리스트에서 가장 큰 간선의 개수를 가진 노드가 몇개 인지 구한다.

 

문제 해결 과정을 조금더 자세하게 서술하면 아래와 같다.

1. 2차원 리스트를 통해 인접리스트 방식으로 그래프를 만든다.

2. 1번 노드를 큐에 담는다. 1번노드를 방문처리해준다.

3. 큐에서 담긴 데이터를 제거한다.(큐는 가장 먼저 들어간 데이터가 먼저 추출되는 자료구조)

4. 3에서 꺼낸 데이터(노드)와 연결된 다음 노드들의 방문여부를 체크하고 방문하지 않았다면 큐에 담는다. 큐에 담으면서 방문 처리를 해준다. 방금 큐에 담은 노드까지의 최단 경로 간선의 수는 이전 노드(직전 3번 단계에서 추출한 노드)까지 이동한 간선의 수에 1을 더해준 값이고 이를 기록한다.

5. 큐에 데이터가 모두 제거될 때 까지 3,4를 반복한다.

6. 각 노드별 최단 경로(1노드에서 각 노드까지 이동하는데 필요한 간선의 수) 데이터에서 최대 값을 구한다.

7. 6에서 구한 최대값과 같은 노드들의 수를 반환한다.

 

 

코드

from collections import deque

def solution(n, vertex):
    answer = 0
    edges_cnt = [0]*(n+1)
    checked = [False]*(n+1)

    #make graph
    graph = [[] for _ in range(n+1)]

    for node in vertex:
        graph[node[0]].append(node[1])
        graph[node[1]].append(node[0])

    #BFS
    q = deque()
    q.append(1)
    checked[1] = True
    while q:
        cur = q.popleft()
        for next in graph[cur]:
            if not checked[next]:
                checked[next] = True
                q.append(next)
                edges_cnt[next] = edges_cnt[cur] + 1

    max_cnt = max(edges_cnt)
    return edges_cnt.count(max_cnt)