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

문제설명

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

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

제한사항

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

전체코드(Python)

def distance(node,start):
    # 방문한 node를 체크하는 배열
    check = [-1 for i in range(len(node))]
    # check에 시작점의 배열을 0으로 저장(나 자신은 거리가 0이므로)
    check[start] = 0
    # 확인할 노드들을 저장하는 공간에 노드의 번호와 거리를 저장한다.
    queue = []
    queue.append((start,0))
    # 확인할 노드가 없을때 까지 계속 반복문을 순회한다.
    while len(queue) !=0:
        # 확인할 노드의 정보를 하나 꺼낸다.
        n = queue.pop(0)
        # 확인할 노드와 연결된 노드의 정보를 하나씩 확인한다.
        while len(node[n[0]])>0:
            # 만일 방문하지 않은 노드라면 노드의 거리와 확인할 노드 공간에 추가한다.
            if check[node[n[0]][0]] == -1:
                queue.append((node[n[0]][0],n[1]+1))
                check[node[n[0]][0]] = n[1]+1
            # 방문여부와 상관없이 확인한 정보는 제거한다.
            node[n[0]].pop(0)
    # 가장 거리가 먼 노드의 거리를 찾아야 하므로 저장한 거리중 가장 큰 값을 m에 저장한다.
    m = max(check)    
    # 가장 거리가 먼 값들의 개수를 반환한다.
    return len(list(filter(lambda x:x==m,check)))
def solution(n, edge):
    # 노드의 관계를 입력할 공간을 선언
    node = [[] for _ in range(n)]
    # 연결정보를 보면서 노드의 관계를 node에 넣는다.
    for i in range(len(edge)):
        node[edge[i][0]-1].append(edge[i][1]-1)
        node[edge[i][1]-1].append(edge[i][0]-1)
    
    return distance(node,0)

혹시라도 정정할 내용이나 추가적으로 필요하신 정보가 있다면 댓글 남겨주시면 감사하겠습니다.

오늘도 Jindory 블로그에 방문해주셔서 감사합니다.

 

[참조]

https://programmers.co.kr/learn/courses/30/lessons/49189