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

문제 정보

제목 : 가장 먼 노드

난이도 : Lv.3

사용 언어 : Python

문제 링크

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

프로그래머스

 

문제 설명

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

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

 

제한 사항

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

입출력 예

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

 

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

---

나의 풀이

BFS를 통해 문제를 해결했습니다. graph defaultdict를 리스트형으로 지정하여 edge에 들어있는 간선에 대한 정보를 저장합니다. 간선은 양방향이기 때문에 s->e로 가는 방향과 e->s로 가는 방향 둘다 각각 저장합니다. BFS함수를 정의하여 실행합니다. 가장 멀리 떨어진 노드가 몇개인지를 return 해 answer에 저장하여 return 합니다.

BFS 함수

방문 여부를 체크하기 위해 visited 리스트를 n+1길이만큼 0으로 선언& 초기화합니다. 1번 노드로부터 가장 멀리 떨어진 노드를 구할 것이므로 deque에는 1을 저장하고, visited리스트에는 1번 노드의 방문 체크에 1을 저장합니다. 그다음 queue에 요소가 있는 동안 반복하는 while루프를 이용해 현재 노드를 구해서 다음 노드를 확인하는데 이때, 다음 노드를 방문 안했다면 현재노드+1을 저장하고 queue에 다음 노드를 추가합니다. while루프의 반복이 끝나면 visited의 최댓값을 구해서 그 값을 count하고 return합니다.

 

코드

from collections import defaultdict,deque

def solution(n, edge):
    answer = 0
    graph = defaultdict(list)
    
    # 그래프 정보 graph defaultdict에 추가함
    for s,e in edge :
        graph[s].append(e)
        graph[e].append(s)
    
    answer = BFS(n,graph) # BFS 수행해서 return 값 저장
    return answer

def BFS(n,graph) :
    visited = [0]*(n+1) # 방문 체크
    queue = deque([1])
    visited[1] = 1 # 1번 노드 방문 여부
    while(queue) :
        curNode = queue.popleft() # 현재 방문한 노드
        for nextNode in graph[curNode]:
            if(visited[nextNode] == 0) : # 다음 노드를 방문 안했다면 1 더해서 방문 표시하고 queue에 추가함
                visited[nextNode] = visited[curNode] + 1
                queue.append(nextNode)
    return(visited.count(max(visited)))