그래프 표현과 탐색 - 인접 행렬·리스트, BFS·DFS

이 장에서 배우는 것

앞 장에서 만든 트라이는 글자를 따라 내려가며 단어를 찾았다. 이번에는 한 지점에서 여러 방향으로 갈 수 있고, 이미 지나온 지점으로 돌아올 수도 있는 연결을 다룬다. 지하철 노선에서 출발역과 도착역이 주어졌을 때 어떤 역을 거쳐야 하는지 구하는 상황이다. 연결을 저장하는 방법과 연결을 따라가는 순서를 직접 구현한다.

역의 이름을 출력하는 것보다 중요한 일은 내부 상태를 설명하는 것이다. 어느 역이 대기 중인지, 언제 방문했다고 표시하는지, 연결을 몇 번 확인했는지 코드로 드러낸다. 자료구조를 사용하는 풀이에서 한 걸음 안으로 들어가, 그 풀이를 받치는 저장 공간과 연산을 만든다.

• 그래프의 정점과 간선을 구분하고 인접 행렬과 인접 리스트로 같은 연결을 저장한다.
• 고정 크기 배열로 만든 큐와 스택을 이용해 탐색 순서를 확인한다.
• 가중치가 없는 연결에서 최소 이동 횟수와 실제 경로를 구한다.
• 연결 확인 횟수와 삽입·꺼내기 횟수를 세어 시간 복잡도를 설명한다.
• 마지막에 내장 자료구조를 사용한 구현과 결과 및 연산 횟수를 비교한다.

문제 상황

작은 교통 안내 도구를 만든다고 하자. 사용자는 가람역에서 바다역으로 가는 방법을 알고 싶어 한다. 노선 데이터에는 서로 바로 이어진 역의 쌍이 들어 있다. 바로 이어진 두 역 사이를 이동할 때마다 이동 횟수는 하나 늘어난다. 여기서는 운행 시간, 배차 간격, 환승 대기 시간을 계산하지 않는다.

가람역에는 나루역과 다솔역으로 가는 연결이 있다. 나루역은 라온역으로 이어지고, 다솔역은 라온역과 마루역으로 이어진다. 라온역과 마루역에서는 바다역으로 갈 수 있다. 길이 갈라지고 다시 합쳐지므로, 자식 방향으로만 내려가는 구조로는 이 관계를 그대로 나타내기 어렵다.

요구사항을 두 가지로 나누면 구현 방향이 선명해진다. 첫째, 출발역에서 갈 수 있는 모든 역을 빠짐없이 확인한다. 둘째, 바다역까지 가장 적은 연결을 지나는 경로를 구한다. 둘 다 연결을 따라가지만, 어떤 순서로 대기 중인 역을 꺼내느냐에 따라 얻는 정보가 달라진다.

연결을 저장하는 두 가지 방법

연결의 양 끝에 있는 대상을 정점(vertex), 두 정점을 잇는 관계를 간선(edge)이라고 한다. 정점과 간선을 함께 나타낸 구조가 그래프(graph)다. 전공 수업에서는 역을 정점으로, 바로 이동할 수 있는 역 사이의 연결을 간선으로 모델링한다고 표현한다. 모델링은 문제에서 필요한 대상과 관계만 골라 표현하는 일이다.

이번 연결은 양쪽으로 이동할 수 있다. 이를 무방향 그래프라고 부른다. 한쪽으로만 이동할 수 있는 연결이라면 방향 그래프다. 코드에서는 역에 0부터 5까지 번호를 붙인다. 이름은 출력에만 쓰고, 연결과 방문 정보는 번호로 다룬다. 정점 수는 V, 무방향 간선 수는 E라고 적는다.

인접 행렬(adjacency matrix)은 모든 정점 쌍에 칸을 하나씩 배정한다. 인접하다는 말은 간선 하나로 바로 이어졌다는 뜻이다. 행이 출발 정점, 열이 도착 정점이다. 연결이 있으면 1, 없으면 0을 넣는다. 무방향 연결이므로 행과 열을 바꾼 자리에도 같은 값을 넣는다. 코드에서는 행 번호에 V를 곱한 뒤 열 번호를 더해 일차원 배열의 위치를 구한다.

인접 리스트(adjacency list)는 정점마다 실제 이웃만 이어 둔다. 이름에 리스트가 들어가지만 Python의 list 메서드로 만들 필요는 없다. 이번 구현은 head 배열에 첫 연결의 번호를 저장하고, to 배열에는 이웃 정점을, link 배열에는 다음 연결의 번호를 저장한다. 연결이 끝났다는 표시는 -1이다. 앞서 연결 리스트를 만들 때 사용한 연결 방식을 정점마다 하나씩 두는 셈이다.

무방향 간선 하나는 이웃 기록 두 개가 된다. 가람에서 나루로 가는 기록과 나루에서 가람으로 가는 기록이 각각 필요하기 때문이다. 입력 순서를 유지하려고 tail 배열에 마지막 기록도 저장한다. 이 배열 덕분에 새 기록을 뒤에 붙일 때 기존 기록을 끝까지 따라가지 않는다.

표현 방식에 따라 필요한 저장 공간과 확인 비용이 달라진다

작업	인접 행렬	인접 리스트	이번 예
저장 공간	O(V²)	O(V + E)	행렬 36칸, 이웃 14개
두 정점의 연결 확인	O(1)	O(출발 정점의 이웃 수)	가람의 이웃은 2개
한 정점의 이웃 순회	O(V)	O(그 정점의 이웃 수)	가람에서 6칸 또는 2개 확인
간선 추가	O(1)	빈 공간과 tail이 있으면 O(1)	고정 용량 안에서 추가

O는 입력이 커질 때 연산량이 어떤 비율로 증가하는지 나타내는 표기다. O(1)은 정점 수가 늘어도 필요한 작업 수가 일정한 경우다. O(V)는 정점 수에 비례하고, O(V²)는 정점 수의 제곱에 비례한다. 정확한 초 단위 실행 시간을 뜻하지 않는다. 전공 수업에서는 이를 점근적 시간 복잡도라고 부른다.

이번 코드의 모든 작업 공간은 크기를 먼저 정한 배열이다. [0] * 크기 같은 고정 크기 list는 저장 칸을 확보하는 용도로만 사용한다. 직접 구현하는 부분에서는 append, pop, dict, set, deque를 사용하지 않는다. 그래프는 생성 시 간선 용량을 받고, 탐색용 배열은 정점 수만큼 확보한다.

대기 순서가 탐색의 성질을 정한다

큐로 가까운 정점부터 확인하기

너비 우선 탐색(BFS, breadth-first search)은 먼저 발견한 정점을 먼저 꺼낸다. 따라서 먼저 들어온 값을 먼저 내보내는 큐가 필요하다. 큐는 읽을 위치와 쓸 위치를 따로 둔다. 위치가 배열 끝에 도달하면 나머지 연산으로 처음으로 돌아간다. 전공 수업에서는 이런 저장 방식을 원형 큐라고 부른다.

방문 표시는 큐에서 꺼낼 때가 아니라 큐에 넣을 때 한다. 라온역은 나루역과 다솔역 양쪽에서 발견할 수 있다. 첫 발견 시 표시하지 않으면 라온역이 두 번 들어갈 수 있다. 이번 구현은 거리 배열을 -1로 채워 미발견 상태를 표시한다. 출발역의 거리는 0이고, 처음 발견한 이웃의 거리는 현재 거리에 1을 더한 값이다.

거리의 단위는 간선 개수다. 모든 간선을 같은 비용으로 취급하므로, 거리 1인 정점을 처리하는 동안 발견하는 새 정점의 거리는 2가 된다. 큐는 이 순서를 유지한다. 그래서 처음 기록한 거리가 최소 이동 횟수다. 전공 수업에서 가중치가 없는 최단 거리라고 부르는 값이다.

거리와 함께 이전 정점도 기록한다. 라온을 나루에서 처음 발견했다면 라온의 이전 정점은 나루다. 바다에서 이전 정점을 거슬러 올라가면 바다, 라온, 나루, 가람이 나온다. 이를 역순으로 출력하면 출발역에서 도착역까지의 경로가 된다. 같은 길이의 경로가 여러 개라면 이웃을 확인하는 순서가 선택 결과를 정한다.

스택으로 최근 발견한 정점부터 확인하기

깊이 우선 탐색(DFS, depth-first search)은 가장 최근에 넣은 정점을 먼저 꺼내도록 스택을 사용한다. 스택은 사용 중인 칸 수를 다음 삽입 위치로 삼는다. 꺼낼 때는 칸 수를 하나 줄이고 그 위치의 값을 읽는다. 재귀 호출 대신 이 스택을 직접 만들어 대기 상태를 확인한다.

이번 구현도 스택에 넣을 때 방문 표시를 한다. 따라서 정점마다 최대 한 번만 들어가며, 스택 용량 V로 충분하다. 이웃을 앞에서부터 넣으면 나중에 넣은 이웃이 먼저 나온다. 여기서 사용하는 반복 방식은 재귀로 이웃을 앞에서부터 방문하는 방식과 방문 순서가 다를 수 있다. 실행 결과는 이 코드가 정한 순서를 보여 준다.

깊이 우선 탐색으로도 도달 가능한 역을 찾을 수 있지만, 처음 발견한 경로가 최소 이동 경로라는 보장은 없다. 이번 장에서는 거리 계산을 너비 우선 탐색에 맡기고, 깊이 우선 탐색은 대기 구조를 바꾸면 순서가 어떻게 달라지는지 확인하는 데 사용한다.

연산 횟수를 무엇으로 셀 것인가

시간 복잡도를 실험하려면 무엇을 한 번으로 셌는지 먼저 정해야 한다. 그래프 순회에서는 연결 후보 하나를 확인할 때마다 1을 센다. 인접 행렬은 값이 0인 칸도 확인하므로 포함한다. 인접 리스트는 저장된 이웃 기록 하나마다 1을 센다. 큐와 스택은 삽입과 꺼내기를 각각 센다.

간선 추가에서는 그래프 배열에 값을 쓰는 횟수를 센다. 행렬은 무방향 간선마다 두 칸을 쓴다. 인접 리스트는 방향별 기록마다 to, link, head 또는 이전 link, tail에 총 네 번 쓴다. 따라서 예제의 일곱 간선을 추가하면 각각 14회와 56회다. 두 값의 크기 차이보다 간선 하나당 일정한 횟수라는 점을 본다.

카운터는 배열 초기화, 정수 계산, 조건 검사, 메모리 관리까지 센 값이 아니다. 큐·스택 연산도 내부 명령 수 대신 공개 연산 호출 수를 센다. 실측 시간과 동일한 척도로 해석하면 안 된다. 다만 반복문의 길이와 자료구조의 성질을 확인하기에는 충분하다.

모든 정점에 도달하는 이번 예제에서 인접 리스트 탐색은 이웃 2E개를 확인하고 정점 V개를 넣고 꺼낸다. 준비 배열을 채우는 일까지 포함하면 O(V + E)다. 행렬 탐색은 각 정점에서 V칸씩 확인하므로 O(V²)다. 연결되지 않은 그래프에서는 출발점에서 도달한 부분만 순회하지만, 탐색 배열을 만드는 데는 여전히 O(V)가 든다.

완성 코드

다음 내용을 main.py에 저장한다. 앞부분은 직접 만든 구현이고, reference 함수만 마지막 비교를 위해 내장 자료구조를 사용한다. 역 번호의 범위는 0 이상 V 미만이며, 입력 간선에는 자기 자신으로 가는 연결과 중복 연결이 없다고 가정한다. 용량을 넘기거나 빈 큐·스택에서 꺼내는 경우에는 예외로 알린다.

class Queue:
    def __init__(self, capacity):
        self.data = [0] * capacity
        self.read = 0
        self.write = 0
        self.size = 0
        self.puts = 0
        self.gets = 0

    def put(self, value):
        if self.size == len(self.data):
            raise OverflowError("큐 용량 초과")
        self.data[self.write] = value
        self.write = (self.write + 1) % len(self.data)
        self.size += 1
        self.puts += 1

    def get(self):
        if self.size == 0:
            raise IndexError("빈 큐")
        value = self.data[self.read]
        self.read = (self.read + 1) % len(self.data)
        self.size -= 1
        self.gets += 1
        return value


class Stack:
    def __init__(self, capacity):
        self.data = [0] * capacity
        self.size = 0
        self.puts = 0
        self.gets = 0

    def put(self, value):
        if self.size == len(self.data):
            raise OverflowError("스택 용량 초과")
        self.data[self.size] = value
        self.size += 1
        self.puts += 1

    def get(self):
        if self.size == 0:
            raise IndexError("빈 스택")
        self.size -= 1
        self.gets += 1
        return self.data[self.size]


class Graph:
    def __init__(self, n, edge_capacity):
        self.n = n
        self.head = [-1] * n
        self.tail = [-1] * n
        self.to = [0] * (2 * edge_capacity)
        self.link = [-1] * (2 * edge_capacity)
        self.used = 0
        self.writes = 0

    def _arc(self, start, end):
        index = self.used
        self.to[index] = end
        self.link[index] = -1
        if self.head[start] == -1:
            self.head[start] = index
        else:
            self.link[self.tail[start]] = index
        self.tail[start] = index
        self.used += 1
        self.writes += 4

    def add(self, a, b):
        if self.used + 2 > len(self.to):
            raise OverflowError("간선 용량 초과")
        self._arc(a, b)
        self._arc(b, a)

    def has_edge(self, a, b):
        checks = 0
        index = self.head[a]
        while index != -1:
            checks += 1
            if self.to[index] == b:
                return True, checks
            index = self.link[index]
        return False, checks


class Matrix:
    def __init__(self, n):
        self.n = n
        self.cells = [0] * (n * n)
        self.writes = 0

    def add(self, a, b):
        self.cells[a * self.n + b] = 1
        self.cells[b * self.n + a] = 1
        self.writes += 2

    def has_edge(self, a, b):
        return self.cells[a * self.n + b] == 1, 1


def bfs(graph, start, matrix_mode=False):
    n = graph.n
    distance = [-1] * n
    parent = [-1] * n
    order = [0] * n
    count = 0
    checks = 0
    queue = Queue(n)
    distance[start] = 0
    queue.put(start)

    while queue.size:
        u = queue.get()
        order[count] = u
        count += 1
        index = 0 if matrix_mode else graph.head[u]
        while (index < n if matrix_mode else index != -1):
            checks += 1
            if matrix_mode:
                v = index
                connected = graph.cells[u * n + v] == 1
                index += 1
            else:
                v = graph.to[index]
                connected = True
                index = graph.link[index]
            if connected and distance[v] == -1:
                distance[v] = distance[u] + 1
                parent[v] = u
                queue.put(v)

    return order, count, distance, parent, checks, queue.puts, queue.gets


def dfs(graph, start):
    seen = [False] * graph.n
    order = [0] * graph.n
    count = 0
    checks = 0
    stack = Stack(graph.n)
    seen[start] = True
    stack.put(start)

    while stack.size:
        u = stack.get()
        order[count] = u
        count += 1
        index = graph.head[u]
        while index != -1:
            checks += 1
            v = graph.to[index]
            if not seen[v]:
                seen[v] = True
                stack.put(v)
            index = graph.link[index]

    return order, count, checks, stack.puts, stack.gets


def route(parent, distance, goal):
    path = [0] * len(parent)
    count = 0
    if distance[goal] == -1:
        return path, count
    current = goal
    while current != -1:
        path[count] = current
        count += 1
        current = parent[current]
    return path, count


def print_names(label, names, values, count, reverse=False):
    print(label, end="")
    for i in range(count):
        if i:
            print(" → ", end="")
        index = count - 1 - i if reverse else i
        print(names[values[index]], end="")
    print()


def reference(n, edges, start):
    from collections import deque

    adjacency = {i: [] for i in range(n)}
    for a, b in edges:
        adjacency[a].append(b)
        adjacency[b].append(a)
    distance = [-1] * n
    parent = [-1] * n
    order = []
    queue = deque([start])
    distance[start] = 0
    checks = 0
    puts = 1
    gets = 0
    while queue:
        u = queue.popleft()
        gets += 1
        order.append(u)
        for v in adjacency[u]:
            checks += 1
            if distance[v] == -1:
                distance[v] = distance[u] + 1
                parent[v] = u
                queue.append(v)
                puts += 1
    return order, len(order), distance, parent, checks, puts, gets


def main():
    names = ("가람", "나루", "다솔", "라온", "마루", "바다")
    edges = ((0, 1), (0, 2), (1, 3), (2, 3),
             (2, 4), (3, 5), (4, 5))
    graph = Graph(len(names), len(edges))
    matrix = Matrix(len(names))
    for a, b in edges:
        graph.add(a, b)
        matrix.add(a, b)

    print("정점 6개, 무방향 간선 7개")
    print(f"간선 추가 배열 쓰기: 리스트 {graph.writes}, 행렬 {matrix.writes}")
    for goal in (2, 5):
        found_l, checks_l = graph.has_edge(0, goal)
        found_m, checks_m = matrix.has_edge(0, goal)
        assert found_l == found_m
        print(f"가람-{names[goal]} 직접 연결: {found_l}, "
              f"확인 리스트 {checks_l}, 행렬 {checks_m}")

    result = bfs(graph, 0)
    order, count, distance, parent, checks, puts, gets = result
    print_names("BFS: ", names, order, count)
    print(f"BFS 연결 확인 {checks}, 큐 넣기 {puts}, 꺼내기 {gets}")

    m = bfs(matrix, 0, True)
    assert m[0] == order and m[2] == distance and m[3] == parent
    print(f"행렬 BFS 연결 확인 {m[4]}, 큐 넣기 {m[5]}, 꺼내기 {m[6]}")

    d_order, d_count, d_checks, d_puts, d_gets = dfs(graph, 0)
    print_names("DFS: ", names, d_order, d_count)
    print(f"DFS 연결 확인 {d_checks}, 스택 넣기 {d_puts}, 꺼내기 {d_gets}")

    print("가람에서의 거리:", end="")
    for i in range(len(names)):
        print(f" {names[i]}={distance[i]}", end="")
    print()
    path, path_count = route(parent, distance, 5)
    print_names("최단 경로: ", names, path, path_count, True)
    print(f"최소 이동 횟수: {distance[5]}")

    built = reference(len(names), edges, 0)
    same = (built[0] == order and built[2] == distance
            and built[3] == parent and built[4:] == result[4:])
    assert same
    print(f"내장 BFS 결과·횟수 일치: {same}")
    print(f"내장 BFS 연결 확인 {built[4]}, 큐 넣기 {built[5]}, 꺼내기 {built[6]}")

    isolated = Graph(3, 1)
    isolated.add(0, 1)
    test = bfs(isolated, 0)
    empty_path, empty_count = route(test[3], test[2], 2)
    assert test[2][2] == -1 and empty_count == 0
    print("도달 불가 검사:", test[2][2], empty_count)

    queue = Queue(2)
    queue.put(7)
    queue.put(8)
    assert queue.get() == 7
    queue.put(9)
    assert queue.get() == 8
    assert queue.get() == 9
    print("원형 큐 재사용 검사: 통과")


if __name__ == "__main__":
    main()

줄별 해설

큐와 스택의 저장 위치

Queue의 data는 확보한 저장 공간이고 size는 실제로 들어 있는 값의 수다. read와 write가 같아도 비었는지 가득 찼는지 구별하려면 size가 필요하다. put의 첫 조건은 덮어쓰기를 막는다. 값을 기록한 다음 write를 한 칸 이동하고, 배열 길이로 나눈 나머지를 구해 위치를 되돌린다. get은 같은 규칙을 read에 적용한다.

두 메서드에는 저장된 원소 수에 따라 길어지는 반복문이 없다. 따라서 넣기와 꺼내기는 각각 O(1)이다. 마지막 재사용 검사는 두 칸을 채우고 하나를 꺼낸 뒤 9를 넣는다. write가 처음 위치로 돌아가도 아직 남은 8이 먼저 나오는지 assert로 확인한다. assert는 조건이 거짓이면 실행을 중단하는 검사문이다.

Stack의 put은 size 위치에 쓰고 size를 늘린다. get은 size를 먼저 줄이므로 가장 마지막에 쓴 위치를 읽는다. 큐와 달리 읽을 위치를 따로 둘 필요가 없다. 이 연산에도 반복문이 없으므로 O(1)이다. 용량 0인 객체는 어떤 값도 넣을 수 없으며, 탐색에서는 유효한 출발 정점이 있는 그래프를 사용한다.

그래프 배열과 간선 추가

Graph의 head와 tail은 정점 수만큼, to와 link는 무방향 간선 용량의 두 배만큼 확보한다. _arc는 한 방향 기록을 추가하는 내부 보조 메서드다. 맨 앞 밑줄은 클래스 내부에서 쓰려는 메서드라는 관례를 나타낸다. index는 새 기록을 넣을 배열 위치이며, 정점 번호와는 다른 번호다.

to[index]에 이웃을 쓰고 link[index]에 끝 표시를 쓴다. 첫 기록이면 head를 바꾸고, 이미 기록이 있으면 기존 마지막 기록의 link를 바꾼다. 그다음 tail을 새 기록으로 옮긴다. 이 네 번의 배열 쓰기를 writes에 더한다. add는 두 기록을 넣을 공간부터 확인하므로, 용량 부족으로 한쪽 연결만 추가되는 상태를 피한다.

has_edge는 head부터 시작해 link를 따라간다. 목표를 만나면 즉시 반환하고, 끝까지 없으면 False를 반환한다. 가람의 기록 순서는 나루, 다솔이므로 다솔을 찾는 데 두 번 확인한다. 바다는 두 기록을 모두 보아도 없으므로 역시 두 번이다. Matrix의 같은 메서드는 계산한 위치 한 칸만 읽는다.

탐색 루프와 최초 발견

bfs의 distance와 parent는 모두 -1로 시작한다. distance[start]만 0으로 바꾸므로 출발점으로 되돌아오는 연결도 중복 삽입을 일으키지 않는다. order는 방문 순서의 저장 공간이고 count는 실제로 채운 칸 수다. 연결되지 않은 정점이 있으면 order의 뒷부분은 사용하지 않는다.

바깥 while은 큐에 값이 남아 있는 동안 돈다. get으로 꺼낸 u를 방문 순서에 기록한 뒤, 안쪽 while에서 연결 후보를 확인한다. matrix_mode가 참이면 열 번호 0부터 n 직전까지 보고, 거짓이면 head와 link를 따라간다. 두 표현의 차이를 이 부분에 모아 두었으므로 거리와 이전 정점을 기록하는 규칙은 공유한다.

connected and distance[v] == -1은 실제 연결이며 아직 발견하지 않은 정점만 통과시킨다. 거리와 이전 정점을 기록한 다음 큐에 넣는 세 줄이 한 묶음이다. 이번 코드는 모든 도달 가능한 정점을 확인하려고 목적지 발견 후에도 계속 돈다. 그래서 모든 정점이 연결된 예제에서 큐 넣기와 꺼내기가 각각 6회다.

dfs에서도 seen[v]를 True로 바꾸는 줄이 stack.put보다 앞에 있다. 가람에서 나루와 다솔을 차례로 넣으면 다솔이 먼저 나온다. 다솔에서 라온과 마루를 넣으면 마루가 먼저 나온다. 라온은 이미 스택에 있으므로 바다에서 라온을 다시 넣지 않는다. 이 과정을 따라가면 출력에 나타난 순서를 얻는다.

경로 복원과 비교 검사

route는 도착점의 거리가 -1이면 길이 0인 경로를 반환한다. 그렇지 않으면 이전 정점을 따라가며 배열을 채운다. 출발점의 parent는 -1이므로 거기서 멈춘다. 경로에 들어 있는 정점 수를 L이라고 하면 이 과정은 O(L)이다. 현재 함수는 먼저 V칸을 확보하므로 함수 전체의 시간과 추가 공간은 O(V)다.

print_names는 reverse가 참일 때 뒤에서부터 읽어 경로를 출력한다. 출력용 문자열을 계속 누적하는 대신 이름을 차례로 출력한다. reference는 비교 경계를 분명히 한 내장 구현이다. 정수 키를 가진 dict와 이웃용 list, 큐용 deque를 사용한다. 연결 입력 순서를 같게 유지하므로 방문 순서뿐 아니라 선택된 이전 정점까지 일치한다.

same은 방문 순서, 거리, 이전 정점, 세 종류의 연산 횟수를 비교한다. 이 일치는 알고리즘 수준의 처리량이 같다는 뜻이다. 내장 구현의 내부 명령 수나 실행 시간이 같다는 뜻은 아니다. 끝의 isolated 검사는 출발점과 연결되지 않은 정점의 거리와 경로 길이를 확인한다. 이처럼 정상 경로 외의 상태도 실행 가능한 검사로 남긴다.

실행 결과

Python 3.12 이상의 환경에서 다음 명령으로 문법을 검사하고 실행한다. 첫 명령은 문법 오류가 없으면 별도 문장을 출력하지 않는다. 프로그램에는 난수가 없고 이웃 저장 순서가 고정되어 있으므로 실행 결과도 일정하다.

python3 -W error -m py_compile main.py
python3 main.py

정점 6개, 무방향 간선 7개
간선 추가 배열 쓰기: 리스트 56, 행렬 14
가람-다솔 직접 연결: True, 확인 리스트 2, 행렬 1
가람-바다 직접 연결: False, 확인 리스트 2, 행렬 1
BFS: 가람 → 나루 → 다솔 → 라온 → 마루 → 바다
BFS 연결 확인 14, 큐 넣기 6, 꺼내기 6
행렬 BFS 연결 확인 36, 큐 넣기 6, 꺼내기 6
DFS: 가람 → 다솔 → 마루 → 바다 → 라온 → 나루
DFS 연결 확인 14, 스택 넣기 6, 꺼내기 6
가람에서의 거리: 가람=0 나루=1 다솔=1 라온=2 마루=2 바다=3
최단 경로: 가람 → 나루 → 라온 → 바다
최소 이동 횟수: 3
내장 BFS 결과·횟수 일치: True
내장 BFS 연결 확인 14, 큐 넣기 6, 꺼내기 6
도달 불가 검사: -1 0
원형 큐 재사용 검사: 통과

인접 리스트의 14회에는 같은 무방향 간선을 양쪽 끝에서 확인하는 일이 포함된다. 행렬의 36회에는 연결이 없는 칸과 자기 자신을 가리키는 대각선 칸도 포함된다. 이 예제 하나로 증가율을 증명할 수는 없지만, 카운터가 반복문의 범위를 그대로 반영하는지는 확인할 수 있다.

정점만 있고 간선이 없는 경우에도 출발점 하나는 방문한다. 반대로 간선이 촘촘하면 이웃 기록 수가 정점 수의 제곱에 가까워질 수 있다. 그래서 인접 리스트의 O(V + E)가 모든 입력에서 행렬보다 작은 작업량을 뜻하지는 않는다. 필요한 질문이 연결 존재 여부인지, 이웃 전체 순회인지 먼저 구분해야 한다.

실무에서 자주 틀리는 것

꺼낼 때만 발견 표시하기

다음 코드는 꺼낼 때 표시하므로, 아직 대기 중인 정점을 다른 연결에서 다시 넣을 수 있다. 여기서는 정점당 한 번만 넣는다는 용량 계산까지 깨진다. 거리와 이전 정점도 최초 발견 시 함께 정해야 한다.

# 잘못된 삽입 부분: 표시가 꺼내는 쪽에만 있다.
if distance[v] == -1:
    queue.put(v)

# 고친 삽입 부분
if distance[v] == -1:
    distance[v] = distance[u] + 1
    parent[v] = u
    queue.put(v)

이 수정은 단순히 중복 출력을 가리는 조치가 아니다. 큐 안에 같은 정점이 여러 번 쌓이지 않게 하여 저장 공간과 처리 횟수를 함께 제한한다. 완성 코드의 puts가 정점 수와 같은 이유도 이 순서에 있다.

무방향 간선을 한쪽에만 기록하기

입력의 쌍을 출발점과 도착점으로만 해석하면 반대 방향의 이동이 사라진다. 가람에서 바다로 가는 검사는 통과해도 바다에서 가람으로 돌아오는 검사는 실패할 수 있다. 방향의 의미를 데이터 규칙과 맞춰야 한다.

# 잘못된 무방향 추가
graph._arc(a, b)

# 고친 무방향 추가: 공개 메서드가 양쪽을 기록한다.
graph.add(a, b)

방향 그래프를 만들 때는 한쪽 기록만 두는 것이 맞다. 중요한 점은 간선 수와 이웃 기록 수를 구분하는 것이다. 이번 구현에서 E는 입력의 쌍 수이고, 실제 이웃 기록은 2E개다.

스택에서 처음 찾은 길을 최단 경로라고 부르기

깊이 우선 탐색은 가까운 순서를 유지하지 않는다. 경로가 우연히 짧게 나오는 입력만으로 올바름을 판단하면 안 된다. 최소 이동 횟수가 요구사항이면 큐의 선입선출 순서가 필요하다. 선입선출은 먼저 들어온 것을 먼저 꺼낸다는 뜻이다.

# 잘못된 선택: DFS 방문 순서는 최단 거리 정보가 아니다.
order, count, checks, puts, gets = dfs(graph, 0)

# 고친 선택: 거리와 이전 정점을 BFS에서 얻는다.
order, count, distance, parent, checks, puts, gets = bfs(graph, 0)
path, path_count = route(parent, distance, 5)

간선마다 소요 시간이 다르면 최소 이동 횟수와 최소 시간이 달라진다. 이번 distance에 분 단위 시간을 더한다고 해결되지 않는다. 이 장의 최단 거리 성질은 모든 연결을 같은 비용으로 취급한다는 조건 안에서 성립한다.

사용하지 않은 배열 칸까지 결과로 읽기

고정 크기 배열의 길이는 결과 개수와 다르다. 도달 가능한 정점이 둘뿐이어도 order는 V칸이다. 남은 칸의 0을 실제 방문으로 해석하면 출발역이 반복해서 보인다. 도달하지 못한 목적지의 경로도 따로 판정해야 한다.

# 잘못된 출력: 확보한 모든 칸을 방문 결과로 읽는다.
print_names("방문: ", names, order, len(order))

# 고친 출력: 실제로 채운 칸만 읽는다.
print_names("방문: ", names, order, count)

# 경로가 있는지 먼저 판단한다.
if distance[5] == -1:
    print("도달할 수 없다")
else:
    path, path_count = route(parent, distance, 5)
    print_names("경로: ", names, path, path_count, True)

용량과 사용량을 구분하는 규칙은 큐, 스택, 이웃 기록에도 동일하게 적용된다. 배열 길이는 최대 저장량을 말하고, size나 used나 count는 현재 의미 있는 부분을 말한다.

한눈에 보기

구현의 불변 조건과 실제 연산 횟수를 함께 기억한다

대상	유지할 조건	시간 복잡도	예제 확인
큐·스택	사용량이 용량을 넘지 않는다	넣기·꺼내기 O(1)	각 탐색에서 각각 6회
인접 리스트 추가	무방향 간선은 기록 두 개다	간선당 O(1)	배열 쓰기 56회
리스트 BFS·DFS	넣기 전에 발견 표시한다	O(V + E)	연결 확인 각각 14회
행렬 BFS	꺼낸 정점의 모든 열을 본다	O(V²)	연결 확인 36회
경로 복원	최초 발견의 이전 정점을 따른다	현재 구현 전체 O(V)	정점 4개, 이동 3회

탐색을 이해하는 기준은 역 이름을 외우는 데 있지 않다. 대기 구조의 앞이나 뒤에서 무엇을 꺼내는지, 발견 표시가 언제 바뀌는지, 어떤 연결 후보를 세는지 설명할 수 있으면 다른 연결 데이터에도 같은 구현을 적용할 수 있다. 다음 장에서는 경로를 순서대로 방문하는 일과는 다른 질문인, 두 대상이 같은 그룹에 속하는지를 다룬다.

연습 문제

1. 정점 두 개와 간선 하나인 그래프를 만들고, 리스트 BFS와 행렬 BFS의 연결 확인 횟수를 비교하라. 큐 넣기와 꺼내기 횟수도 검사하라.
2. 정점 네 개 중 0과 1, 2와 3만 연결하라. 0에서 시작했을 때 방문 수, 거리 배열, 3까지의 경로 길이를 확인하라.
3. 네 정점을 고리로 연결하라. BFS와 DFS 모두 넣기 횟수가 네 번인지 검사하라. 방문 표시를 삽입 시점에 하는 이유를 설명하라.
4. 원래 노선의 간선 입력 순서에서 (0, 2)를 (0, 1)보다 앞에 두라. 바다까지의 최단 거리와 선택 경로가 어떻게 달라지는지 검사하라.

정답과 해설

아래 코드는 완성 코드의 함수와 클래스를 그대로 사용한다. 각 조각을 main 함수 안에 추가해 실행하면 assert로 결과를 확인할 수 있다. 별도 외부 패키지는 필요하지 않다.

두 정점의 연결 확인 횟수

g = Graph(2, 1)
m = Matrix(2)
g.add(0, 1)
m.add(0, 1)
a = bfs(g, 0)
b = bfs(m, 0, True)
assert a[4] == 2
assert b[4] == 4
assert a[5] == a[6] == 2
assert b[5] == b[6] == 2

리스트는 정점마다 이웃 하나씩 총 두 기록을 확인한다. 행렬은 두 정점에서 두 열씩 총 네 칸을 확인한다. 두 방식 모두 실제 발견한 정점은 두 개이므로 큐 연산 횟수는 같다. 연결 표현의 비용과 대기 구조의 비용을 구분해서 읽어야 한다.

서로 떨어진 두 연결

g = Graph(4, 2)
g.add(0, 1)
g.add(2, 3)
r = bfs(g, 0)
path, length = route(r[3], r[2], 3)
assert r[1] == 2
assert r[2] == [0, 1, -1, -1]
assert length == 0
assert r[4] == 2

2와 3 사이에 간선이 있어도 출발점 0에서는 그쪽으로 갈 수 없다. 그래프 전체를 저장했다는 사실과 한 번의 탐색으로 전체를 방문한다는 사실은 다르다. 마지막 비교의 list 리터럴은 정답 검사용이며 탐색의 저장 방식을 바꾸지 않는다.

고리에서 중복 삽입 막기

g = Graph(4, 4)
for a, b in ((0, 1), (1, 2), (2, 3), (3, 0)):
    g.add(a, b)
b = bfs(g, 0)
d = dfs(g, 0)
assert b[5] == b[6] == 4
assert d[3] == d[4] == 4
assert b[4] == d[2] == 8

고리를 따라가면 이미 발견한 정점을 다시 만난다. 그러나 발견 표시는 대기 구조에 넣기 전에 끝나므로 다시 넣지 않는다. 정점은 네 번 처리하지만 무방향 간선 네 개의 양쪽 기록은 모두 확인하므로 연결 확인은 여덟 번이다.

같은 거리에서 다른 경로 선택하기

g = Graph(6, 7)
for a, b in ((0, 2), (0, 1), (1, 3), (2, 3),
             (2, 4), (3, 5), (4, 5)):
    g.add(a, b)
r = bfs(g, 0)
path, length = route(r[3], r[2], 5)
assert r[2][5] == 3
assert length == 4
assert path[0] == 5
assert path[1] == 3
assert path[2] == 2
assert path[3] == 0

가람에서 다솔을 먼저 발견하므로 라온의 이전 정점이 다솔이 된다. 출력 방향으로 읽은 경로는 가람, 다솔, 라온, 바다다. 이동 횟수는 여전히 3이다. 최단 거리는 하나의 값이어도 그 거리를 이루는 경로는 여러 개일 수 있으며, 이번 구현은 입력 순서로 그중 하나를 결정한다.