[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번 노드입니다.

입출력 graph

 

접근 방법

문제에 따른 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)