[Programmers] 그래프(Graph) - 가장 먼 노드

해당 글은 프로그래머스의 그래프 탐색 기법에 해당하는 문제를 풀고 작성했음을 밝힙니다. 해당 문제를 풀면서 참고한 블로그 출처를 아래에 밝힙니다.
프로그래머스 문제 링크 - https://programmers.co.kr/learn/courses/30/lessons/49189
문제 풀이 참고 - https://velog.io/@younge/Python-프로그래머스-가장-먼-노드-그래프

문제 설명

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

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

제한사항

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

입출력 예

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

입출력 예 설명

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

접근 방법

문제에 따른 BFS, DFS 선택 - https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90
문제 관련 이슈(스포: DFS를 사용하면 통과가 안되는 이유) - https://programmers.co.kr/questions/12681

해당 문제는 모양적으로 Graph임이 명확히 드러나기도 합니다. 그리고 node 개수와 edge 개수를 보면 각각 20,000개와 50,000개까지 있을 수 있습니다. 10,000개 이상이면 코딩테스트에서는 효율성을 본다는 의미고 어떤 알고리즘적인 접근이 필요하다는 뜻입니다. 브루트포스처럼 완전탐색법으로는 풀 수 없다는 겁니다.! ㅠ
Graph > Graph 탐색 방법(BFS, DFS)가 무엇인지 공부했습니다.
탐색 알고리즘에 해당하는 BFS와 DFS의 사용에 따른 차이를 확인했습니다.
- BFS와 DFS는 복잡도 측면에서는 동일한 수식을 따릅니다. 하지만, 경우에 따라 너비 단위로 접근하는 것인 BFS가 좋을지 깊이 단위로 접근하는 DFS가 좋을지 달라집니다.
- 주로, 최단 거리에 대한 언급이 있을 때에는 BFS를 통해 문제를 접근합니다. 하지만, 최단 거리 문제더라도 edge마다의 특성이 존재한다면 DFS로 접근하는 것이 바람직하다고 합니다. 특성을 가지는 edge에 대한 문제는 아직 못 풀어봤지만 궁금하시다면 아래의 블로그들에서 확인 가능합니다.
  - https://11001.tistory.com/77
  - https://godgod732.tistory.com/7
해당 문제는 자식 노드가 없는 터미널 노드 중에서도 최단 경로로 접근할 수 있는 터미널 노드의 개수를 구하는 문제이기 때문에 BFS가 유리합니다. 그리고, DFS로 풀 경우 아래와 같은 문제가 발생할 수 있다고 질문사항에 언급되어 있었습니다.

DFS의 경우 깊이가 깊어지는 간선을 먼저 탐색하기 때문에, (1, 2) , (1, 3), (2, 3) 이렇게 연결되있을 때 3번 노드는 1번 노드로부터 1의 깊이를 가지지만 DFS로 탐색할 경우 1->2->3 순으로 탐색하기 때문에 3번 노드가 1번 노드로부터 2의 깊이를 가지게 되서 모순이 발생

해당 문제 같은 경우, 다익스트라 알고리즘으로도 접근이 가능하다고 스터디하면서 피드백을 받았습니다. 해당 방법도 추후 공부한 뒤에 추가하겠습니다.

풀이 코드

쉐도잉한 코드 - https://velog.io/@younge/Python-프로그래머스-가장-먼-노드-그래프

30분 시간제한을 두다보니 잘 안 풀려서 younge 블로그님의 코드를 보면서 공부했습니다. 해당 블로그 코드에서 제가 코드 리팩토링을 진행한 것은 아래와 같습니다.

graph를 만드는 부분의 코드를 defaultdict 모듈을 사용해서 dictionary value를 list type으로 정의된 변수로 정의
start 변수 추가, 변수명 변경을 통해 BFS 알고리즘을 동작 원리를 이해하기 쉽도록 수정
각 코드마다 주석 추가

from collections import deque
from collections import defaultdict

def solution(n, edges):
    """
        n(int): 데이터가 저장되어 있는 노드의 개수 => 굳이 구하지 않더라도, edge로부터도 얻을 수 있는 정보긴 함.
        edge(array): 노드간의 관계를 나타내는 간선
        min_dist(int): 1번 노드에서 가장 멀리 떨어진 노드의 개수
    """
    # graph를 dict 형태로 정의
    graph = defaultdict(list)
    # graph의 노드 관계를 dict로 변환
    for edge in edges:
        graph[edge[0]].append(edge[1])
        graph[edge[1]].append(edge[0])
    # print(graph)
    
    # BFS
    # 시작 노드 1번으로 정의
    start = 1
    # 방문했던 노드 파악을 위한 list
    visited = [start] + [0]*n
    # 시작 노드를 포함하는 queue 정의
    queue = deque([start])
    # 가장 끝단에 있는 node까지의 최단 거리를 저장하기 위한 같은 depth에 있는 node들의 개수
    depth_nodes = 0
    while len(queue)!=0:
        # depth_nodes(int): 같은 depth 상에 있는 node의 개수
        depth_nodes = len(queue)
        # 동일 depth에 있는 원소들을 왼쪽부터 탐색
        for c in range(depth_nodes):
            node = queue.popleft()
            # 현재 위치한 node와 인접한(adjacency) node들을 탐색
            for adj_node in graph[node]:
                # 방문하지 않은 노드에 도달할 경우 index를 통해 visited 원소값을 1로 변경
                # (방문하지 않은 상태: 0, 방문한 상태: 1)
                if visited[adj_node-1] == 0:
                    visited[adj_node-1] = 1
                    # 자식 node인 인접한 node들을 저장(같은 depth에 있는 node들 저장하는 작업)
                    queue.append(adj_node)
    return depth_nodes

출력

변수 중에 graph를 출력해보면, 각 노드 번호마다 인접한 노드들의 번호가 있는 리스트를 담은 딕셔너리 형태로 graph가 정의됐음을 알 수 있습니다. 해당 과정을 진행해줘야 이후 BFS 알고리즘을 적용하기 쉽습니다.

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

실행 시간

출처 코드를 실행시킨 시간을 테스트 1~9 사이로 비교해보면, 생각보다 실행시간의 변화가 있었습니다. 테스트 1, 2, 3을 제외하고는 모두 실행 시간이 단축했으며 특히 테스트 9에서 약 4배에 이르는 실행시간이 단축됐습니다. 대신, 메모리 차지는 제가 수정한 코드가 좀더 큼을 알 수 있습니다.

테스트 1 〉	통과 (0.02ms, 10.4MB)
테스트 2 〉	통과 (0.02ms, 10.3MB)
테스트 3 〉	통과 (0.05ms, 10.3MB)
테스트 4 〉	통과 (0.22ms, 10.4MB)
테스트 5 〉	통과 (0.84ms, 10.6MB)
테스트 6 〉	통과 (2.50ms, 11MB)
테스트 7 〉	통과 (22.17ms, 17.5MB)
테스트 8 〉	통과 (32.24ms, 20.9MB)
테스트 9 〉	통과 (30.56ms, 20.5MB)

출처 코드의 실행 시간

테스트 1 〉	통과 (0.02ms, 10.2MB)
테스트 2 〉	통과 (0.02ms, 10.3MB)
테스트 3 〉	통과 (0.04ms, 10.3MB)
테스트 4 〉	통과 (0.32ms, 10.3MB)
테스트 5 〉	통과 (1.37ms, 10.6MB)
테스트 6 〉	통과 (3.89ms, 10.9MB)
테스트 7 〉	통과 (35.90ms, 17.5MB)
테스트 8 〉	통과 (48.70ms, 20.6MB)
테스트 9 〉	통과 (120.70ms, 20.5MB)

저작자표시 비영리 변경금지