[프로그래머스] 8. 가장 먼 노드

프로그래머스의 가장 먼 노드 문제는 그래프 문제이다. 그래프 문제를 풀이할때 떠올려야할 자료구조는 BFS, DFS, 이진탐색, 동적계획법 정도이다. 해당 문제는 BFS 를 통해 해결하였다.

 

from collections import deque, defaultdict

def bfs(visited, graph):
    deq = deque()
    deq.append(1)

    while deq:
        node = deq.popleft()

        if visited[node-1][0] == 1:  # 이미 방문 한 노드는 건너뛰기.
            continue

        visited[node-1][0] = 1  # 방문처리.
        edge = graph[node]  # 해당 노드의 간선에 해당하는 노드들.
        check_deq = set(deq)

        for e in edge:
            if visited[e - 1][0] == 1 or e in check_deq:
                continue
            deq.append(e)
            visited[e-1][1] = visited[node-1][1] + 1

    return visited

def create_graph(edge):
    graph = defaultdict(list)

    for e in edge:
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])

    return graph

def solution(n, edge):
    answer = 0
    graph = create_graph(edge)
    visited = [[0, 0] for _ in range(n)] # visit, dist
    visited = bfs(visited, graph)
    max_dist = max(visited)[1]

    for v in visited:
        if v[1] == max_dist:
            answer += 1

    return answer

n = 6
vertex = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]
print(solution(n, vertex))

 

문제에서 내가 가장 눈여겨 보았던 부분은 "1번 노드로부터 가장 멀리 떨어진" 라는 문장이었다. 즉 모든 TestCase에서의 시작 노드는 1번노드 라는 뜻이다.

 

우선, vertex가 주어저 있기 때문에 노드간 연결되어있는 노드를 Dict 형태로 구성하였다(create_graph). 또한 노드의 방문여부를 만들기 위해 visited 리스트를 만들어주었다. 2차원 리스트로써 0번 인덱스는 방문여부를 나타내고, 1번 인덱스는 1번노드로부터 떨어진 거리를 담을 수 있도록 하였다.

 

bfs의 시작은 1번노드부터 이기 때문에 deque에 1번 node를 넣어주고 반복문을 시작한다. queue에 담겨져있는 노드 하나를 꺼내고 해당노드가 방문을 했던 노드인지 아닌지를 검사한다. 만약 방문한 노드라면 다음 반복문으로 넘어가고, 아니라면 방문처리를 해준 후 연결되어있는 노드를 Dict에서 가져온다. 연결되어있는 노드들의 방문여부를 검사한다. 방문한 노드라면 건너뛰고, 방문하지 않은 노드라면 거리를 1만큼 증가시킨다.

 

모든 노드를 방문했다면 queue에 더이상 노드가 남아있지 않게되므로 while 조건을 탈출하게된다. visited에는 노드번호와 1번 노드로부터 떨어진 거리가 모두 반영이 되어있으므로 max값에 해당하는 노드가 몇개인지 세어주면 된다.