[코딩 테스트] 프로그래머스 - 가장 먼 노드

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

 

더 자세한 설명 - programmers.co.kr/learn/courses/30/lessons/49189 

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

 

풀이

1. 먼저, 노드들의 연결 관계를 나타내주는 dictionary를 만든다.

문제가 다음과 같은 구성일 때,

conn이라는 dictionary는 다음과 같은 형태를 띌 것.

conn = {1: [2, 3],
        2: [1, 3, 4, 5],
        3: [1, 2, 4, 6],
        4: [2, 3],
        5: [2],
        6: [3]
        }

1번 노드는 2, 3번 노드와 연결, 2번 노드는 1, 3, 4, 5번 노드와 연결, ...되기 때문이다.

 

2. 각 노드에 다다르기 위한 거리를 저장하는 list, steps를 초기화한다.

steps = [0] * (n + 1)

3. 너비 우선 탐색(BFS)를 시도한다.

- 현재 노드와 연결된 노드들을 먼저 다 살피면서,

    - 이 중 (1번 노드)가 있다면 탐색 끝이고,

    - 없다면 현재 노드와 연결된 노드들에 연결된 노드들을 살피면 되기 때문이다.

 

=> BFS (선입선출로직!) 를 위해서 deque를 사용한다. 

 

4. 탐색을 끝낸 후에는 steps에서 최댓값이 중복되어 나타나는 수를 answer로 반환!

 

코드 구현

 

from collections import deque

def solution(n, vertex):
    # organize a connectivity dictionary
    conn = {}
    for x, y in vertex:
        conn[x] = conn.get(x, []) + [y]
        conn[y] = conn.get(y, []) + [x] 
        
    # keep record of steps req'd to reach each node
    steps = [0] * (n + 1)
    
    # start from the node #1
    q = deque([1])
    countEdges = 0
    while q:
    	# explore the nodes connected to the current node
        n = len(q)
        for i in range(n):
            curr = q.popleft()
            # if the node is not visited yet
            if steps[curr] == 0:
                steps[curr] = countEdges
                # add the nodes connected to this node if they are not visited
                # &they are not node no.1
                for i in conn[curr]:
                    if steps[i] == 0 and i != 1:
                        q.append(i)                
        countEdges += 1
        
    answer = steps.count(max(steps))
    
    return answer