[알고리즘] 그래프

그래프(Graph)란?

정의는 다양하나 그래프 이론에서의 그래프란 객체의 일부 쌍들이 '연관되어' 있는 객체 집합 구조를 말한다. 그 중에서도 코딩테스트에서 자주 등장하는 그래프 순회를 다뤄보겠다.

그래프 순회

"그래프 순회란 그래프 탐색이라고도 불리우며 그래프의 각 정점을 방문하는 과정을 말한다."

그래프 순회에는 크게 깊이우선탐색(Depth First Search, 이하 DFS)와 너비 우선 탐색(Breadth First Search, 이하 BFS)가 있으며, 이에 대해서는 별도의 분류가 존재하므로 거기서 자세히 다루기로 한다.

그래프vs트리

그래프와 트리의 차이점은 한마디로,
"트리는 순환 구조를 갖지 않는 그래프"라는 점이다.
즉, 트리보다 그래프가 광의의 개념으로 트리는 순환 구조를 갖지 않는다.

파이썬(Python)

파이썬의 장점 중 하나는 다양한 라이브러리를 지원한다는 것이다. 이왕 파이썬을 코딩테스트 대비 언어로 선정한 이상 파이썬의 장점을 적극 활용해야하지 않겠는가.
나의 경우, collections의 defaultdict(list)를 이용해 그래프를 구성하는 것을 선호하는 편이며,
그래프 문제에서 자주 나오는 방문표시는 때에 따라서 리스트와 딕셔너리를 적절히 활용하는 편이다.
아래는 예시이다.

from collections import defaultdict, deque
def solution(n, edges):
    # 그래프 구성
    graph = defaultdict(list)
    for edge in edges:
        graph[edge[0]].append(edge[1])
        graph[edge[1]].append(edge[0])
        
        # graph 출력결과 : defaultdict(<class 'list'>, {3: [6, 4, 2, 1], 6: [3], 4: [3, 2], 2: [3, 1, 4, 5], 1: [3, 2], 5: [2]})

프로그래머스 고득점 kit 문제

• 가장 먼 노드 (lv3)
• 순위 (lv3)
• 방의 개수 (lv5)

참고문헌

박상길, 『파이썬 알고리즘 인터뷰』, 책만