프로그래머스: 가장 먼 노드(파이썬, BFS)

그래프의 root node로부터 가장 멀리 떨어진 노드들의 개수를 구하는 문제이다. 문제의 조건에서 가장 멀리 떨어진 노드의 정의에 대하여 최단경로로 이동했을 때, 간선의 개수가 가장 많은 노드라 명시하였다.

 

그래프의 탐색이기에 우선 그래프를 인접 행렬로 표현하였고 그 다음으로 그래프의 탐색방법인 DFS, BFS중 고민하였는데 BFS로 푸는 것이 더 효율적이라는 생각이 들었다. 왜냐하면 DFS는 모든 경로를 전부 탐색하여 비교하기에 BFS보다 시간복잡도측에서 비효율적이기 때문이다. 

 

일반적으로 그래프를 탐색하거나 간선들의 가중치가 모두 같을 때 최단경로를 구한다면 BFS가 효율적이다. 혹은 DP를 쓰던지..

 

따라서 BFS로 문제를 풀었다.

기본적인 BFS 구현 코드를 사용하였고 거기에 queue에 자식 노드들을 넣을 때 부모 노드의 간선의 갯수+1을 같이 넣음으로써 자식 노드의 간선 개수를 세도록 하였다.

BFS가 끝난 후 BFS의 과정을 담은 배열을 간선의 갯수를 기준으로 내림차순 정렬하여 값이 같지 않을 때까지 반복문을 돌려 간선값이 최대인 개수를 세는 방식으로 문제를 풀었다.

from collections import deque


def bfs(graph, visited):
    global result
    # 인접 행렬은 부모 인덱스에 자식을, 자식 인덱스에 부모를 넣으므로 미리 visited[1]을 True로 해놔야 재방문하지 않는다.
    visited[1] = True
    # 노드의 번호와 간선 갯수를 deque에 넣음 ex: 노드의 번호 1의 간선 갯수는 0
    queue = deque([(1,0)])
    while queue:
        cash = queue.popleft()
        node, vertex = cash[0], cash[1]
        for child in graph[node]:
            if not visited[child]:
                visited[child] = True
                queue.append((child, vertex+1))
                # 이전 노드의 간선 갯수에 1을 더하여 다음 노드의 간선 갯수를 셈
                result.append((child, vertex+1))


def solution(n, edge):
    global result
    result = []
    graph = [[] for _ in range(n+1)]
    visited = [False for __ in range(n+1)]
    for e in edge:
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])
    bfs(graph, visited)
    answer = 1
    result.sort(key=lambda x:x[1], reverse=True)
    i = 0
    while i < len(result)-1 and result[i][1] == result[i+1][1]:
        answer += 1
        i += 1
    return answer