그래프와 연결 관계 탐색하기

왜 그래프가 필요한가

트리는 부모와 자식 관계가 분명한 계층 구조였다. 폴더 구조나 조직도처럼 위에서 아래로 내려가는 관계를 표현하기 좋았다. 하지만 세상의 모든 관계가 계층적인 것은 아니다.

예를 들어 친구 관계를 생각해 보자. A와 B가 친구이고, B와 C가 친구이며, C와 A도 친구일 수 있다. 여기에는 반드시 맨 위의 루트가 필요하지 않다. 도로 지도도 마찬가지다. 도시와 도시가 여러 방향으로 연결되어 있고, 어떤 길은 짧고 어떤 길은 길다. 컴퓨터 네트워크에서는 여러 장비가 복잡하게 서로 연결된다.

이처럼 여러 대상이 자유롭게 연결된 구조를 표현할 때 사용하는 자료구조가 그래프다.

그래프는 크게 두 가지로 이루어진다.

• 정점: 연결 관계에 등장하는 대상이다. 사람, 도시, 컴퓨터, 웹 페이지 등이 될 수 있다.

• 간선: 정점과 정점을 잇는 연결이다. 친구 관계, 도로, 케이블, 링크 등이 될 수 있다.

예를 들어 사람 4명이 있고 친구 관계가 다음과 같다고 하자.

• 1번과 2번은 친구다.

• 1번과 3번은 친구다.

• 2번과 4번은 친구다.

여기서 사람 1, 2, 3, 4는 정점이고, 친구 관계는 간선이다. 알고리즘 문제에서는 보통 정점 수와 간선 목록이 입력으로 주어진다.

정점 수: 4
간선:
1 2
1 3
2 4

그래프를 배우는 이유는 단순하다. 연결된 대상을 빠짐없이 탐색하고, 어떤 대상까지 갈 수 있는지 확인하고, 가장 가까운 경로를 찾기 위해서다.

AI 생성 이미지

그래프의 여러 형태

그래프는 간선의 성격에 따라 여러 종류로 나뉜다. 이름은 어렵게 보일 수 있지만, 실제 의미는 간단하다.

무방향 그래프

무방향 그래프는 연결에 방향이 없는 그래프다. A와 B가 연결되어 있으면 A에서 B로 갈 수 있고, B에서 A로도 갈 수 있다.

친구 관계가 대표적이다. 1번과 2번이 친구라면 보통 1번도 2번의 친구이고, 2번도 1번의 친구다.

1 -- 2

입력으로 1 2가 들어오면, 내부적으로는 다음 두 관계를 모두 저장해야 한다.

1에서 2로 갈 수 있다.
2에서 1로 갈 수 있다.

방향 그래프

방향 그래프는 간선에 방향이 있는 그래프다. A에서 B로 갈 수 있다고 해서 반드시 B에서 A로 갈 수 있는 것은 아니다.

SNS 팔로우 관계를 생각하면 쉽다. 내가 어떤 사람을 팔로우한다고 해서 그 사람이 나를 팔로우하는 것은 아니다.

1 -> 2

이 경우에는 1에서 2로 갈 수 있다만 저장한다. 반대 방향은 따로 입력되지 않았다면 없는 관계다.

가중치 그래프

가중치 그래프는 간선에 값이 붙어 있는 그래프다. 이 값은 거리, 비용, 시간, 위험도처럼 문제에서 의미를 가진다.

도시 사이의 도로를 생각해 보자.

서울 -- 부산: 400
서울 -- 대전: 160
대전 -- 부산: 250

여기서 400, 160, 250은 간선의 가중치다. 단순히 연결 여부만 보는 문제가 아니라 비용이 가장 작은 경로를 찾아야 한다면 가중치를 함께 저장해야 한다.

이번 장에서는 먼저 연결 여부와 탐색 순서에 집중한다. 가중치가 있는 최단 경로는 더 발전된 알고리즘에서 다루지만, 지금은 그래프에 이런 형태가 있다는 점만 이해하면 충분하다.

그래프를 저장하는 두 가지 방법

그래프 문제를 풀려면 먼저 입력으로 들어온 연결 관계를 프로그램 안에 저장해야 한다. 대표적인 방법은 인접 행렬과 인접 리스트다.

인접 행렬

인접 행렬은 정점과 정점의 연결 여부를 표로 저장하는 방식이다. 정점이 n개라면 기본적으로 n × n 크기의 표를 만든다고 생각하면 된다.

다만 알고리즘 문제에서는 정점 번호가 1번부터 n번까지 주어지는 경우가 많다. 이 번호를 그대로 배열 인덱스로 쓰고 싶다면 실제 코드에서는 n + 1 크기로 만드는 편이 안전하다. 예를 들어 정점 1과 2가 연결되어 있으면 matrix[1][2]를 참으로 표시한다. 무방향 그래프라면 matrix[2][1]도 참으로 표시한다.

1 -- 2
1 -- 3

의사코드는 다음과 같다.

matrix = (n + 1) x (n + 1) 크기의 false 표

for each (a, b) in edges:
    matrix[a][b] = true
    matrix[b][a] = true  # 무방향 그래프일 때만

만약 정점 번호를 0번부터 n - 1번까지 쓰는 방식이라면 n × n 크기로 만들면 된다. 중요한 것은 정점 번호와 배열 인덱스를 헷갈리지 않는 것이다.

인접 행렬의 장점은 두 정점이 연결되어 있는지 빠르게 확인할 수 있다는 점이다.

if matrix[a][b] == true:
    a와 b는 연결되어 있다

이 확인은 배열 한 칸을 바로 보는 일이므로 시간 복잡도는 O(1)이다.

하지만 단점도 있다. 정점 수가 많으면 표가 너무 커진다. 정점이 10,000개라면 10,000 × 10,000칸이 필요하다. 실제 간선이 몇 개 없어도 모든 칸을 만들어야 한다.

그래서 인접 행렬은 정점 수가 작거나, 간선이 매우 많거나, 두 정점의 연결 여부를 자주 확인해야 할 때 적합하다.

인접 리스트

인접 리스트는 각 정점마다 직접 연결된 이웃만 저장하는 방식이다.

예를 들어 다음 그래프가 있다고 하자.

1 -- 2
1 -- 3
2 -- 4

인접 리스트로 저장하면 다음과 같다.

1: 2, 3
2: 1, 4
3: 1
4: 2

의사코드는 다음과 같다.

graph = 빈 리스트 n + 1개

for each (a, b) in edges:
    graph[a].append(b)
    graph[b].append(a)  # 무방향 그래프일 때만

여기서도 정점 번호가 1번부터 시작한다고 가정했기 때문에 n + 1개를 만들었다. 0번부터 시작하는 정점 번호를 쓴다면 n개면 충분하다.

인접 리스트의 장점은 실제로 존재하는 간선만 저장한다는 점이다. 정점은 많지만 연결이 드문 그래프에서 메모리를 아낄 수 있다.

또한 어떤 정점에서 갈 수 있는 이웃을 하나씩 확인하기 좋다.

for next in graph[x]:
    next는 x와 연결된 정점이다

그래프 탐색에서는 보통 어떤 정점의 이웃을 모두 살펴보는 일이 많다. 그래서 많은 문제에서 인접 리스트를 더 자주 사용한다.

정리하면 선택 기준은 다음과 같다.

깊이 우선 탐색: 한 길을 끝까지 들어가기

그래프를 저장했다면 이제 탐색할 수 있다. 탐색은 연결된 정점들을 규칙에 따라 방문하는 과정이다.

첫 번째 방법은 깊이 우선 탐색, 줄여서 DFS다. DFS는 한 정점에서 시작해 갈 수 있는 한 길을 끝까지 들어간다. 더 이상 갈 곳이 없으면 직전 갈림길로 돌아와 다른 길을 살펴본다.

미로를 떠올리면 쉽다. 한 방향으로 계속 걸어가다가 막히면 뒤로 돌아와 아직 가 보지 않은 길을 선택하는 방식이다.

다음 그래프에서 1번부터 탐색한다고 하자.

1 -- 2 -- 4
|
3

인접 리스트가 다음 순서라고 하자.

1: 2, 3
2: 1, 4
3: 1
4: 2

DFS는 보통 다음처럼 움직인다.

1 방문
2 방문
4 방문
다시 2로 돌아옴
다시 1로 돌아옴
3 방문

방문 순서는 1, 2, 4, 3이 된다. 단, 인접 리스트의 순서가 달라지면 방문 순서도 달라질 수 있다. 중요한 것은 한 길을 깊게 들어간다는 원리다.

DFS는 재귀 함수로 자연스럽게 구현할 수 있다. 트리 순회를 배웠다면 비슷하게 느껴질 것이다. 다만 그래프에는 순환이 있을 수 있으므로, 이미 방문한 정점을 다시 방문하지 않도록 표시해야 한다.

visited = 정점 수만큼 false로 초기화

function dfs(x):
    visited[x] = true
    x를 처리한다

    for next in graph[x]:
        if visited[next] == false:
            dfs(next)

여기서 visited가 매우 중요하다. 무방향 그래프에서 1과 2가 연결되어 있다면, 1에서 2로 가고 다시 2에서 1로 돌아갈 수 있다. 방문 표시가 없다면 같은 두 정점을 끝없이 오가게 된다.

재귀 대신 스택으로도 DFS를 구현할 수 있다.

function dfs_stack(start):
    stack = 빈 스택
    stack.push(start)

    while stack이 비어 있지 않다면:
        x = stack.pop()

        if visited[x] == true:
            continue

        visited[x] = true
        x를 처리한다

        for next in graph[x]:
            if visited[next] == false:
                stack.push(next)

재귀 DFS는 코드가 짧고 구조가 직관적이다. 스택 DFS는 재귀 호출이 너무 깊어질 때 대안이 될 수 있다. 둘 다 핵심은 같다. 최근에 발견한 길을 먼저 따라간다는 점이다.

인접 리스트로 DFS를 수행하면 각 정점과 각 간선을 대체로 한 번씩 확인한다. 시간 복잡도는 O(V + E)다. 여기서 V는 정점 수, E는 간선 수다.

너비 우선 탐색: 가까운 곳부터 넓게 퍼지기

두 번째 대표 탐색은 너비 우선 탐색, 줄여서 BFS다. BFS는 시작점에서 가까운 정점부터 차례대로 방문한다.

물결이 퍼지는 모습을 떠올리면 좋다. 물에 돌을 던지면 중심에서 가까운 곳부터 원이 넓어진다. BFS도 시작 정점에서 거리 1인 정점들을 먼저 보고, 그다음 거리 2인 정점들을 본다.

BFS는 큐를 사용한다. 큐는 먼저 들어온 값이 먼저 나가는 자료구조였다. 먼저 발견한 정점을 먼저 처리하기 때문에 가까운 정점부터 순서대로 탐색할 수 있다.

다음 그래프를 보자.

1 -- 2 -- 4
|
3 -- 5

1번에서 시작하면 가까운 순서는 다음과 같다.

거리 0: 1
거리 1: 2, 3
거리 2: 4, 5

BFS 의사코드는 다음과 같다.

function bfs(start):
    queue = 빈 큐
    visited[start] = true
    queue.enqueue(start)

    while queue가 비어 있지 않다면:
        x = queue.dequeue()
        x를 처리한다

        for next in graph[x]:
            if visited[next] == false:
                visited[next] = true
                queue.enqueue(next)

BFS에서는 보통 큐에 넣는 순간 방문 표시를 한다. 그래야 같은 정점이 여러 번 큐에 들어가는 일을 막을 수 있다.

BFS의 강력한 장점은 가중치가 없는 그래프에서 최단 거리를 구할 수 있다는 점이다. 여기서 최단 거리는 간선을 몇 번 지나야 도착하는지를 뜻한다.

거리까지 구하려면 distance 배열을 함께 사용한다.

function bfs_distance(start):
    queue = 빈 큐
    distance = 정점 수만큼 -1로 초기화

    distance[start] = 0
    queue.enqueue(start)

    while queue가 비어 있지 않다면:
        x = queue.dequeue()

        for next in graph[x]:
            if distance[next] == -1:
                distance[next] = distance[x] + 1
                queue.enqueue(next)

이 코드에서는 distance[next] == -1인지 확인하는 것이 방문 여부 확인의 역할도 한다. 아직 거리가 정해지지 않은 정점만 큐에 넣는 것이다.

distance[next] = distance[x] + 1이라는 한 줄이 핵심이다. x까지 오는 데 필요한 간선 수를 이미 알고 있으므로, x의 이웃인 next까지는 한 칸 더 가면 된다.

예를 들어 1번에서 시작해 4번까지의 최단 거리를 구한다고 하자.

1 -> 2 -> 4

간선을 2번 지나므로 거리는 2다. BFS는 가까운 정점부터 방문하기 때문에, 어떤 정점에 처음 도착했을 때의 거리가 곧 최단 거리다.

단, 이 설명은 모든 간선의 비용이 같을 때만 맞다. 도로마다 거리나 비용이 다르다면 단순 BFS만으로는 부족하다. 그때는 가중치를 고려하는 다른 최단 경로 알고리즘이 필요하다.

DFS와 BFS를 언제 선택할까

DFS와 BFS는 모두 그래프를 탐색하는 기본 도구다. 둘 중 하나만 항상 좋은 것은 아니다. 문제에서 무엇을 요구하는지에 따라 선택한다.

DFS가 어울리는 경우는 다음과 같다.

• 연결된 모든 정점을 끝까지 탐색해야 할 때

• 어떤 경로가 존재하는지 확인할 때

• 여러 가능한 경우를 깊게 따라가며 확인할 때

• 재귀적으로 구조를 파고드는 문제가 자연스러울 때

BFS가 어울리는 경우는 다음과 같다.

• 시작점에서 가까운 순서대로 탐색해야 할 때

• 가중치가 없는 그래프에서 최단 거리를 구할 때

• 몇 번 이동해야 도착하는지 구할 때

• 같은 거리의 후보를 단계별로 처리해야 할 때

예를 들어 1번 컴퓨터와 연결된 모든 컴퓨터 수를 구하라는 문제라면 DFS와 BFS 모두 사용할 수 있다. 연결된 정점을 빠짐없이 방문하기만 하면 되기 때문이다.

반면 1번 칸에서 목표 칸까지 최소 몇 번 이동해야 하는가처럼 최단 이동 횟수를 묻는다면 BFS가 더 적합하다. 가까운 곳부터 탐색하므로 처음 목표에 도착했을 때의 이동 횟수가 최소가 된다.

연결되지 않은 그래프도 생각하기

그래프의 모든 정점이 하나로 이어져 있다고 가정하면 안 된다. 다음처럼 두 덩어리로 나뉜 그래프도 있다.

1 -- 2 -- 3

4 -- 5

1번에서 DFS나 BFS를 시작하면 1, 2, 3은 방문할 수 있지만 4, 5는 방문할 수 없다. 이런 경우 전체 그래프를 모두 탐색하려면 모든 정점을 시작 후보로 확인해야 한다.

count = 0
visited = 정점 수만큼 false로 초기화

for v from 1 to n:
    if visited[v] == false:
        dfs(v)
        count = count + 1

여기서 count는 연결된 덩어리의 개수다. 이런 덩어리를 연결 요소라고 한다. 그래프 문제에서는 연결 요소의 개수를 구하거나, 각 연결 요소의 크기를 구하는 유형이 자주 나온다.

다만 위 설명은 보통 무방향 그래프를 기준으로 이해하면 된다. 방향 그래프에서는 A에서 B로 갈 수 있다와 B에서 A로 갈 수 있다가 다를 수 있으므로, 문제에서 요구하는 연결의 의미를 더 조심해서 읽어야 한다.

자주 틀리는 부분

그래프 문제에서 가장 흔한 실수는 방문 표시를 빼먹는 것이다. 트리는 부모에서 자식으로 내려가면 보통 다시 부모로 돌아가는 간선을 따로 생각하지 않아도 된다. 하지만 그래프는 다르다. 특히 무방향 그래프에서는 양쪽으로 이동할 수 있으므로 방문 표시가 없으면 무한 반복에 빠질 수 있다.

두 번째 실수는 방향 그래프와 무방향 그래프를 혼동하는 것이다. 무방향 그래프에서는 a -> b와 b -> a를 모두 저장한다. 방향 그래프에서는 입력된 방향만 저장한다. 문제에서 양방향, 서로 이동 가능, 일방통행, A가 B를 신뢰한다 같은 표현을 주의 깊게 읽어야 한다.

세 번째 실수는 인덱스 범위다. 정점 번호가 1부터 시작하는지 0부터 시작하는지 확인해야 한다. 정점이 1번부터 n번까지라면 배열 크기를 n + 1로 잡아 1번부터 그대로 사용하는 방식이 실수를 줄여 준다.

네 번째 실수는 BFS에서 방문 표시를 너무 늦게 하는 것이다. 큐에서 꺼낼 때 방문 표시를 하면 같은 정점이 큐에 여러 번 들어갈 수 있다. 보통은 큐에 넣는 순간 방문 표시를 한다.

다섯 번째 실수는 가중치가 있는 그래프에 BFS를 그대로 적용하는 것이다. BFS가 최단 거리를 보장하는 것은 간선 하나를 지날 때마다 비용이 모두 같을 때다. 간선마다 비용이 다르면 간선 수가 적은 경로와 비용이 작은 경로가 다를 수 있다.

핵심 정리

그래프는 정점과 간선으로 여러 대상의 연결 관계를 표현하는 자료구조다. 트리보다 자유로운 구조이며, 친구 관계, 지도, 네트워크처럼 복잡하게 얽힌 문제를 다룰 수 있다.

그래프를 저장할 때는 인접 행렬과 인접 리스트를 선택할 수 있다. 연결 여부를 빠르게 확인해야 하고 정점 수가 작다면 인접 행렬이 편하다. 정점 수가 크고 실제 간선이 적다면 인접 리스트가 보통 더 적합하다.

DFS는 한 길을 끝까지 들어가는 탐색이다. 재귀나 스택으로 구현하며, 경로 존재 확인이나 전체 방문에 자주 사용한다. BFS는 가까운 곳부터 넓게 퍼지는 탐색이다. 큐로 구현하며, 가중치가 없는 그래프에서 최단 이동 횟수를 구할 때 특히 강력하다.

그래프 문제를 만나면 먼저 세 가지를 확인하자.

1. 정점과 간선이 무엇인가?

2. 방향이 있는가, 없는가? 가중치가 있는가?

3. 모든 정점을 방문하면 되는가, 최단 거리가 필요한가?

이 질문에 답할 수 있으면 그래프 문제의 출발점은 잡은 것이다. 이후의 구현은 인접 리스트, 방문 배열, DFS 또는 BFS라는 기본 도구로 차근차근 만들어 갈 수 있다.