C-3: 그래프 표현 — 정점을 자유롭게 잇고, 두 방법으로 담는다

안녕하세요, 홍순구 튜터입니다. 지난 시간 우리는 완전 이진트리를 배열 한 장에 담아 "가장 급한 것"을 O(log n)에 꺼내는 힙을 만들었습니다. 그리고 이런 말을 남겨 뒀죠. "트리는 사실 사이클 없이 연결된 특수한 그래프다. 그 제약을 풀면 그래프가 된다." 오늘 그 제약을 풀어 봅니다.

그래프(graph)는 코딩테스트에서 가장 자주 나오는 주제 중 하나입니다. 미로 탈출, 섬의 개수, 친구 추천, 최단 경로 — 겉보기엔 다 달라 보이지만 속을 열어 보면 전부 "정점과 간선으로 이뤄진 그래프 문제"예요. 그래서 그래프를 컴퓨터에 어떻게 담느냐가 이 뒤에 이어질 탐색 알고리즘 전체의 발판이 됩니다.

오늘 핵심은 딱 두 가지입니다. 그래프를 담는 두 방법 — 인접 행렬과 인접 리스트 — 을 직접 짜 보고, "언제 무엇을 쓸지"를 메모리와 시간의 트레이드오프로 고르는 겁니다.

 오늘의 여정 — 비선형 자료구조의 마지막, 그래프

   용어·종류           →   두 가지 표현            →   실전·다음으로
   정점·간선·차수            인접 행렬  (공간 O(V²))       defaultdict(list)
   방향/무방향·가중치         인접 리스트 (공간 O(V+E))     DFS·BFS(E-2)의 발판

💡 오늘 수업의 핵심 — "정점을 간선으로 자유롭게 이은 그래프를, 인접 행렬과 인접 리스트라는 두 방법으로 담고 트레이드오프로 고른다"

🎯 학습 목표

• 그래프 용어(정점·간선·차수)와 종류(방향/무방향·가중치)를 안다.
• 인접 행렬과 인접 리스트를 직접 구현하고, 공간·시간의 빅오 트레이드오프로 둘을 견준다.
• 실전에서 defaultdict(list)로 인접 리스트를 만들고, 다음 알고리즘(DFS·BFS)의 발판을 놓는다.

Step 1: "트리의 제약을 풀면 그래프"

먼저 우리가 어디까지 왔는지 지도를 다시 펴 봅시다. 카테고리 B에서 한 줄로 늘어선 선형 자료구조(스택·큐·연결 리스트·해시)를 배웠고, 카테고리 C에서 가지 치는 비선형 자료구조로 넘어왔어요. C-1 트리, C-2 힙, 그리고 오늘 C-3 그래프가 비선형의 마지막입니다.

 선형 (한 줄로 늘어섬)            비선형 (가지 치고 이어짐)
   스택·큐·연결 리스트·해시          트리 (C-1)   힙 (C-2)   그래프 (C-3, 오늘)

지난 시간까지의 트리를 떠올려 볼게요. 트리는 규칙이 엄격했습니다. 부모에서 자식으로 내려가는 한 방향이 있고, 어느 노드로 가는 길도 딱 하나뿐이었죠. 되돌아오는 사이클도 없었고요. 그래프는 이 규칙을 다 풀어 줍니다. 정점끼리 자유롭게, 서로를 가리키며 이어져요.

 트리 (C-1)                        그래프 (C-3)
   부모 → 자식, 한 방향               정점끼리 자유롭게 서로 이음
   어디로 가든 길은 하나              길이 여러 갈래·되돌아오는 사이클도

        1                             0 ─── 1
       / \                            │  ╱  │
      2   3                           2 ─── 3 ─── 4
     / \
    4   5
   사이클 없음·연결                    사이클 있음·자유로운 연결

이 자유로운 구조를 부르는 용어 세 개만 잡고 갑시다. 어렵지 않아요.

• 정점(vertex): 데이터 하나입니다. 사람, 도시, 웹페이지 같은 것들이요. 노드(node)라고도 부릅니다.
• 간선(edge): 두 정점을 잇는 선입니다. 친구 관계, 도로, 링크가 다 간선이에요.
• 차수(degree): 한 정점에 붙은 간선의 수입니다. "이 사람 친구가 몇 명인가"가 곧 차수죠.

그래프가 왜 필요할까요? 세상엔 트리처럼 딱 떨어지는 계층 관계만 있는 게 아니기 때문입니다. 회원과 게시물은 부모-자식으로 정리되지만, 친구 관계는 그렇지 않아요. A가 B의 친구이고 B가 C의 친구인데 A가 다시 C의 친구일 수 있죠. 도시 간 도로도 이리저리 얽히고, 지하철 노선도 순환합니다. 이렇게 계층이 아니라 서로 얽힌 관계를 담는 그릇이 그래프입니다.

🎯 코테에서는 문제 지문에 "정점 N개, 간선 M개가 주어진다", "도시 사이를 잇는 길", "친구 관계", "노드가 연결되어 있다" 같은 표현이 나오면 거의 그래프 문제예요. 미로·섬·네트워크·경로 문제가 전부 여기 속합니다.

💡 한 줄 정리

그래프는 정점(vertex)을 간선(edge)으로 자유롭게 이은 비선형 자료구조다. 트리의 "한 방향·사이클 없음·유일한 경로" 제약을 풀면 그래프가 되고, 계층이 아니라 서로 얽힌 관계(친구·도로·링크)를 담는다.

Step 2: "화살표가 있나, 거리가 있나"

같은 그래프라도 종류가 나뉩니다. 문제를 읽고 "이건 어떤 종류의 그래프인가"를 판별하는 게 모델링의 첫걸음이에요. 두 가지 축만 보면 됩니다. 간선에 방향이 있나, 간선에 무게(가중치)가 있나.

먼저 방향입니다. 인스타그램을 떠올려 보세요. 장원영이 카리나를 팔로우해도, 카리나가 장원영을 팔로우한 건 아니에요. 화살표가 한쪽으로만 갑니다. 이게 방향 그래프(directed graph)예요. 반대로 "서로 친구"는 양쪽이 대등하죠. A가 B의 친구면 B도 A의 친구입니다. 이건 무방향 그래프(undirected graph)예요.

 무방향 (친구 관계)               방향 (인스타 팔로우)
   장원영 ─── 카리나               장원영 ──▶ 카리나
   서로 친구(양쪽 대등)             장원영이 카리나를 팔로우(한쪽만)

   0 ─── 1                         0 ──▶ 1

다음은 가중치입니다. 지금까지 간선은 "이어졌다/아니다"만 표시했어요. 그런데 도시 사이 도로라면 거리가 다르죠. 서울-대전 140km, 대전-부산 200km처럼요. 이렇게 간선에 숫자(무게)가 붙은 게 가중치 그래프(weighted graph)입니다. 이 무게가 거리일 수도, 요금일 수도, 걸리는 시간일 수도 있어요.

 가중치 (도시 간 거리)
   서울 ──140── 대전 ──200── 부산
   숫자 = 간선의 무게(거리·요금·시간 등)

가중치가 없는 그래프에서 최단 경로는 "간선을 가장 적게 거치는 길"이고, 가중치가 있으면 "무게 합이 가장 작은 길"이 됩니다. 앞의 것은 나중에 BFS(E-2)로, 뒤의 것은 다익스트라(F-1)로 푸는데, 오늘은 "이런 구분이 있다"까지만 알아 두면 충분해요.

🎯 코테에서는 지문이 "서로 팔로우" 같은 대칭 관계면 무방향, "A가 B에게 의존한다·선행 과목" 같은 일방 관계면 방향입니다. "거리·비용·시간"이 간선마다 다르게 주어지면 가중치 그래프고요. 이 세 단어를 지문에서 먼저 찾으세요.

💡 한 줄 정리

그래프는 간선의 방향 유무(방향/무방향)와 무게 유무(가중치/비가중치)로 갈린다. 팔로우는 방향, 친구는 무방향, 도로 거리는 가중치다. 문제 지문의 "대칭 관계·일방 관계·거리/비용" 단어가 종류를 알려 준다.

Step 3: "표 한 장으로 — 인접 행렬"

이제 진짜 문제입니다. 정점과 간선을 컴퓨터에 어떻게 담을까요? 첫 번째 방법은 인접 행렬(adjacency matrix)입니다. A-2에서 다뤘던 2차원 배열(격자)을 그대로 씁니다. 격자를 기억하시죠? 그때의 grid[행][열]이 여기선 matrix[정점][정점]이 됩니다.

정점을 0번부터 번호로 매기고, V×V 크기의 표를 만듭니다. matrix[u][v]가 1이면 u와 v 사이에 간선이 있는 거예요(0이면 없음). 우리가 Step 1에서 그린 다섯 정점 그래프를 표로 옮기면 이렇게 됩니다.

 간선: 0-1, 0-2, 1-2, 1-3, 2-3, 3-4  (무방향)

         0  1  2  3  4
     0 [ 0  1  1  0  0 ]     0의 행: 1,2 와 이어짐
     1 [ 1  0  1  1  0 ]     1의 행: 0,2,3 과 이어짐
     2 [ 1  1  0  1  0 ]
     3 [ 0  1  1  0  1 ]
     4 [ 0  0  0  1  0 ]     4의 행: 3 과만 이어짐

무방향이라 표가 대각선을 기준으로 대칭인 게 보이시나요? 0-1 간선은 matrix[0][1]과 matrix[1][0] 양쪽에 다 1로 찍힙니다. 화살표 두 개를 그은 것과 같죠. 코드로 짜 봅시다.

# structures/graph.py

class AdjacencyMatrixGraph:
    def __init__(self, num_vertices):
        self.n = num_vertices
        # V×V 표를 0으로 채운다. 0 = 간선 없음, 그 외 값 = 간선(가중치)
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]

    def add_edge(self, u, v, weight=1, directed=False):
        """u-v 간선을 놓는다. 한 칸만 채우니 O(1). 무방향이면 양쪽을 대칭으로."""
        self.matrix[u][v] = weight
        if not directed:
            self.matrix[v][u] = weight      # 무방향: u→v와 v→u가 같다(대칭)

    def has_edge(self, u, v):
        """u에서 v로 가는 간선이 있나. 표의 한 칸만 보면 되니 O(1)."""
        return self.matrix[u][v] != 0

    def neighbors(self, u):
        """u의 이웃(이어진 정점)을 번호 순으로 모은다. 한 행을 다 훑어 O(V)."""
        return [v for v in range(self.n) if self.matrix[u][v] != 0]

    def degree(self, u):
        """u의 차수(붙은 간선 수). 한 행을 세어 O(V)."""
        return sum(1 for v in range(self.n) if self.matrix[u][v] != 0)

add_edge의 weight 인자를 보세요. 기본값 1을 넣으면 "이어졌다"만 표시하고, 다른 숫자를 넣으면 Step 2의 가중치가 그 칸에 저장됩니다. directed=True면 한쪽만, 아니면 양쪽 대칭으로 찍고요. 표 한 장에 방향·가중치까지 다 담기죠.

실제로 넣고 확인해 보면 이렇게 동작합니다.

edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4)]
mg = AdjacencyMatrixGraph(5)
for u, v in edges:
    mg.add_edge(u, v)

mg.has_edge(1, 3)     # True  (표의 [1][3] 한 칸만 확인)
mg.has_edge(0, 4)     # False (0과 4는 이어지지 않음)
mg.neighbors(1)       # [0, 2, 3]

여기서 빅오를 봅시다. 이 방식의 강점은 has_edge예요. "u와 v가 이어졌나"를 표의 한 칸만 보고 답하니 O(1)입니다. 대신 약점이 있어요. 간선이 하나도 없어도 V×V 칸을 늘 차지하니 공간이 O(V²)입니다. 이웃을 모으려면 한 행 전체를 훑어야 해서 neighbors와 degree는 O(V)고요.

🎯 코테에서는 정점 수가 적고(수백 이하) 간선이 조밀하거나, "두 정점이 이어졌나"를 아주 자주 물어야 하는 문제에서 인접 행렬이 편합니다. 플로이드-워셜 최단 경로(F-1)가 대표적으로 인접 행렬 위에서 도는 알고리즘이에요.

💡 한 줄 정리

인접 행렬은 V×V 표에 간선을 담아, 두 정점이 이어졌는지를 O(1)에 확인한다. 대신 간선이 없어도 V×V 칸을 차지해 공간이 O(V²)이고, 이웃 순회는 한 행을 훑어 O(V)다. 정점이 적고 조밀한 그래프에 어울린다.

Step 4: "이웃만 적어 — 인접 리스트"

인접 행렬의 약점은 낭비였어요. 친구가 두 명뿐인 사람도 전체 인원수만큼의 칸을 차지했죠. 두 번째 방법 인접 리스트(adjacency list)는 이 낭비를 없앱니다. 발상은 단순해요. 각 정점마다 "이 정점과 이어진 이웃 목록"만 들고 있는 겁니다.

우리 다섯 정점 그래프를 인접 리스트로 옮기면 이렇게 됩니다.

   0 → [1, 2]          0은 1,2 와 이어짐
   1 → [0, 2, 3]       1은 0,2,3 과 이어짐
   2 → [0, 1, 3]
   3 → [1, 2, 4]
   4 → [3]             4는 3 과만 이어짐

인접 행렬의 5×5=25칸과 비교해 보세요. 여기선 실제 간선(양방향이라 6×2=12개)만큼만 저장합니다. 간선이 적을수록 이 차이가 커져요. 코드로 봅시다.

class AdjacencyListGraph:
    def __init__(self, num_vertices):
        self.n = num_vertices
        self.adj = [[] for _ in range(num_vertices)]    # 정점마다 이웃 목록 하나

    def add_edge(self, u, v, directed=False):
        """u-v 간선을 놓는다. 목록 맨 뒤에 붙이니 O(1). 무방향이면 양쪽에 넣는다."""
        self.adj[u].append(v)
        if not directed:
            self.adj[v].append(u)           # 무방향: v의 목록에도 u를 넣는다

    def neighbors(self, u):
        """u의 이웃 목록을 그대로 돌려준다. 이미 모여 있어 O(1)."""
        return self.adj[u]

    def has_edge(self, u, v):
        """u에서 v로 가는 간선이 있나. 이웃 목록을 뒤져 O(degree)."""
        return v in self.adj[u]

    def degree(self, u):
        """u의 차수. 이웃 목록 길이라 O(1)."""
        return len(self.adj[u])

add_edge가 하는 일은 목록 맨 뒤에 이웃을 붙이는 것뿐이에요. 무방향이면 양쪽 목록에 서로를 넣죠. Step 2의 "무방향 = 화살표 두 개"가 여기서 append 두 번으로 나타납니다.

lg = AdjacencyListGraph(5)
for u, v in [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4)]:
    lg.add_edge(u, v)

lg.neighbors(1)     # [0, 2, 3]  (이미 모여 있어 바로 반환)
lg.degree(1)        # 3

빅오가 인접 행렬과 거울처럼 뒤집힙니다. 공간은 실제 간선만 담아 O(V+E)예요(정점 V개 + 간선 E개). 이웃 순회는 그 정점의 목록만 보면 되니 낭비 없이 차수만큼, degree도 목록 길이라 O(1)입니다. 대신 "u-v가 이어졌나"는 목록을 처음부터 뒤져야 해서 O(degree)로, 행렬의 O(1)보다 느려요. 이게 맞바꾼 대가입니다.

🎯 코테에서는 실전 그래프 문제의 대부분이 인접 리스트를 씁니다. 대회·채용 문제의 그래프는 보통 간선이 정점 수에 비해 적은 희소 그래프라, 공간 O(V+E)와 알뜰한 이웃 순회가 결정적이거든요. DFS·BFS·다익스트라가 전부 인접 리스트 위를 걷습니다.

💡 한 줄 정리

인접 리스트는 정점마다 이웃 목록만 들고 있어 공간이 O(V+E)로 알뜰하고, 이웃 순회가 차수만큼이라 낭비가 없다. 대신 간선 확인은 목록을 뒤져 O(degree)로 행렬보다 느리다. 간선이 적은 희소 그래프의 기본 표현이다.

Step 5: "언제 표, 언제 목록?"

두 방법을 다 짜 봤으니, 오늘의 핵심 질문에 답할 차례입니다. 인접 행렬과 인접 리스트, 언제 무엇을 고를까요? 이건 암기가 아니라 빅오로 판단하는 거예요. 두 표현을 한 표에 나란히 놓고 봅시다.

판단의 핵심은 "간선이 얼마나 빽빽한가"예요. 정점이 V개일 때 간선은 최대 약 V²개까지 생길 수 있습니다(모든 쌍이 이어진 완전 그래프). 그런데 현실의 그래프는 대부분 그보다 훨씬 적어요. 친구가 아무리 많아도 전 세계 인구만큼은 아니잖아요. 이렇게 간선이 정점 수에 비례하는 정도(E ≈ V 수준)면 희소 그래프, V²에 가까우면 밀집 그래프라고 합니다.

여기에 A-1의 "1초 ≈ 1억 연산" 잣대를 대 봅시다. 정점이 10만 개인 그래프를 인접 행렬로 담으면 10만 × 10만 = 100억 칸이 필요해요. 이건 메모리에 아예 올릴 수가 없습니다. 반면 간선이 20만 개뿐인 희소 그래프라면 인접 리스트는 O(V+E) = 30만 정도로 거뜬하죠. 그래서 코테의 그래프 문제는 대부분 인접 리스트가 정답입니다.

 정점 V = 100,000 일 때

   인접 행렬   :  V² = 100억 칸        → 메모리 초과, 못 올림
   인접 리스트 :  V + E ≈ 30만         → 거뜬함  (간선 E = 20만 가정)

⚠️ 그렇다고 인접 행렬이 쓸모없는 건 아니에요. 정점이 적고(수백 이하) 간선이 빽빽하거나, "두 정점이 이어졌나"를 매우 자주 물어야 하면 O(1) 간선 확인이 빛납니다. 플로이드-워셜(F-1)처럼 모든 쌍의 최단 거리를 다루는 알고리즘은 인접 행렬 위에서 돕니다. 정답은 하나가 아니라 "입력 크기와 연산 패턴을 보고 고르는" 거예요.

🎯 코테에서는 문제의 정점 수 제한을 먼저 보세요. V가 1000 이하로 작으면 인접 행렬도 O(V²) = 100만이라 부담 없고, V가 10만처럼 크면 무조건 인접 리스트입니다. "정점 수의 제곱이 시간·공간 안에 드나"가 첫 판단이에요.

💡 한 줄 정리

간선이 적은 희소 그래프(E ≈ V)는 인접 리스트(공간 O(V+E)), 간선이 빽빽한 밀집 그래프나 간선 확인이 잦으면 인접 행렬(간선 확인 O(1))이 유리하다. 정점 수 제한을 보고 "V²이 시간·공간 안에 드나"로 고른다. 코테는 대개 인접 리스트다.

Step 6: "실전은 defaultdict(list)"

Step 4에서 인접 리스트를 클래스로 직접 짜 원리를 봤어요. 이제 이 과목의 두 번째 트랙, "실전에선 어떻게 쓰나"로 갑니다. 코테에서 그래프를 만날 때 매번 클래스를 짜진 않아요. 파이썬 표준 라이브러리 collections.defaultdict로 몇 줄이면 끝납니다.

먼저 코테의 그래프 입력이 어떻게 생겼는지 봅시다. 보통 이런 식으로 간선 목록이 주어져요.

5 6                간선: 정점 5개, 간선 6개
0 1                (0-1 간선)
0 2                (0-2 간선)
1 2
1 3
2 3
3 4

이 간선 목록을 인접 리스트로 바꾸는 게 첫 일입니다. 그냥 dict를 쓰면 처음 보는 정점 키에서 KeyError가 나요. 아직 목록을 안 만들어 뒀으니까요. defaultdict(list)는 이 문제를 없앱니다. 처음 보는 키를 건드리면 빈 목록을 자동으로 만들어 줘서, 곧바로 append하면 됩니다.

from collections import defaultdict

def build_adjacency_list(edges, directed=False):
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        if not directed:
            adj[v].append(u)
    return adj

이게 전부예요. 간선을 한 번씩만 훑으니 O(E)에 인접 리스트가 완성됩니다. 직접 짠 AdjacencyListGraph가 하던 일과 똑같지만, 정점 수를 미리 안 넘겨도 되고 클래스 정의도 필요 없죠. 실전에선 이 다섯 줄이 표준입니다.

edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4)]
adj = build_adjacency_list(edges)     # 무방향

adj[3]      # [1, 2, 4]
adj[0]      # [1, 2]

방향 그래프면 directed=True를 넘겨 한쪽만 넣으면 됩니다. 선행 과목 관계("A를 들어야 B를 들을 수 있다")나 작업 순서 같은 방향 그래프를 이 한 인자로 다 담아요.

이게 이 과목이 두 트랙을 두는 이유입니다. 직접 구현으로 "인접 리스트가 왜 O(V+E)인지"를 손으로 봤으니, 실전에선 defaultdict(list)를 믿고 씁니다. 원리를 아는 사람은 이 한 줄이 안에서 무슨 일을 하는지 알기에, 언제 이걸 쓰고 언제 set으로 바꿀지(Step 4 질문)를 판단할 수 있어요.

🎯 코테에서는 그래프 문제를 받으면 graph = defaultdict(list)로 시작해 간선을 담는 게 거의 관용구입니다. 무방향이면 양쪽에 넣는 것만 잊지 마세요. 이 한 줄을 빠뜨려 한쪽 방향만 넣는 실수가 그래프 문제의 단골 함정이에요.

💡 한 줄 정리

실전에선 collections.defaultdict(list)로 간선 목록을 O(E)에 인접 리스트로 만든다. 처음 보는 키에 빈 목록을 자동으로 만들어 줘 append만 하면 되고, 무방향이면 양쪽에 넣는다. 직접 구현으로 원리를 본 뒤 실전은 이 관용구를 믿고 쓴다.

adj = {}
for u, v in edges:
    if u not in adj:
        adj[u] = []
    adj[u].append(v)

Step 7: "그래프를 다 만들었으니"

그래프를 담는 두 방법을 다 배웠습니다. 이제 담은 그래프로 뭘 할 수 있는지, 그리고 이게 어디로 이어지는지 보며 오늘을 마무리해요.

가장 기본은 우리가 짠 degree와 neighbors입니다. 차수를 세면 "친구가 가장 많은 사람", "가장 붐비는 교차로"를 찾을 수 있어요. 이웃을 순회하면 "이 정점에서 한 걸음 갈 수 있는 곳"이 나오고요. 이 이웃 순회가 사실 엄청나게 중요합니다. 왜냐하면 그래프 위를 걷는 모든 알고리즘이 결국 "지금 정점의 이웃을 보고, 그중 하나로 이동한다"의 반복이거든요.

 그래프 위를 걷는다는 것

   지금 정점 1 에 있음
     → 이웃 [0, 2, 3] 을 봄        (neighbors)
     → 아직 안 가 본 2 로 이동      (방문 체크 필요!)
     → 다시 2 의 이웃을 봄 ...

여기서 딱 하나가 빠졌어요. "아직 안 가 본"을 어떻게 알까요? 그래프는 사이클이 있어서, 표시를 안 해 두면 왔던 곳을 무한히 맴돌 수 있습니다. 그래서 방문 체크가 필요해요. 어디를 다녀왔는지 집합(set)이나 배열에 기록하며 걷는 거죠. B-3의 집합이 여기서 다시 등장합니다.

이 "이웃을 보며 방문 체크하고 걷는다"에 순서 규칙을 얹으면 두 가지 탐색이 됩니다. 다음에 갈 곳을 스택으로 관리하면 DFS(깊이 우선 탐색), 큐로 관리하면 BFS(너비 우선 탐색)예요. B-1에서 배운 스택과 큐가 바로 여기 쓰입니다. 오늘은 발판까지만 놓고, 실제 걷기는 다음 카테고리에서 만나요.

 오늘의 그래프가 어디로 이어지나

   그래프 (C-3, 오늘)
     + 스택/큐(B-1) + 방문 체크(B-3)  ──▶  DFS·BFS (E-2)   "그래프 위를 걷기"
     + 힙(C-2)                        ──▶  다익스트라 (F-1) "가중치 최단 경로"

지난 시간 힙을 배우며 "우선순위 큐로 가장 가까운 것부터 꺼낸다"를 심어 뒀죠. 그 힙과 오늘의 그래프가 만나면 다익스트라 최단 경로(F-1)가 됩니다. 지도에서 출발지부터 "지금까지 가장 가까운 정점"을 힙으로 계속 꺼내며 이웃으로 뻗어 나가는 거예요. 오늘 그래프를 손에 넣었으니, 다익스트라를 만날 때 절반은 이미 아는 셈입니다.

🎯 코테에서는 "미로 최단 거리", "섬의 개수", "네트워크 연결 요소"가 전부 오늘 만든 그래프 위에서 DFS·BFS로 푸는 대표 유형입니다. 그래프를 인접 리스트로 모델링하는 것까지가 오늘 배운 절반이고, 그 위를 걷는 게 다음 절반이에요.

💡 한 줄 정리

그래프의 이웃 순회는 "지금 정점에서 한 걸음"이고, 사이클 때문에 방문 체크가 반드시 필요하다. 다음 갈 곳을 스택으로 두면 DFS, 큐로 두면 BFS(E-2)가 되고, 힙(C-2)을 더하면 다익스트라(F-1)가 된다. 오늘 그래프 표현이 그 모든 탐색의 발판이다.

마무리

오늘은 비선형 자료구조의 마지막, 그래프를 배웠습니다. 트리의 제약을 풀어 정점을 자유롭게 잇고, 그 얽힘을 인접 행렬과 인접 리스트라는 두 방법으로 담았어요. 그리고 "언제 무엇을 쓸지"를 공간과 시간의 트레이드오프로 골랐습니다. 이걸로 카테고리 C의 세 그릇 — 트리·힙·그래프 — 이 모두 채워졌네요.

오늘 배운 핵심 세 가지

• 💡 하나 — 그래프는 정점을 간선으로 자유롭게 이은 구조다. 트리의 "한 방향·사이클 없음·유일한 경로" 제약을 풀면 그래프가 된다. 방향/무방향, 가중치/비가중치로 종류가 갈리고, 계층이 아니라 얽힌 관계(친구·도로·링크)를 담는다.
• 💡 둘 — 담는 방법은 인접 행렬과 인접 리스트, 둘의 빅오가 거울처럼 뒤집힌다. 행렬은 간선 확인 O(1)·공간 O(V²), 리스트는 공간 O(V+E)·이웃 순회 O(degree). 정점이 많고 간선이 적은 희소 그래프면 인접 리스트, 작고 밀집하거나 간선 확인이 잦으면 인접 행렬이다.
• 💡 셋 — 실전은 defaultdict(list), 그리고 이 위에서 탐색이 돈다. 간선 목록을 O(E)에 인접 리스트로 만들고, 이웃 순회 + 방문 체크로 그 위를 걷는다. 스택이면 DFS, 큐면 BFS(E-2), 힙을 더하면 다익스트라(F-1)다.

다음 시간 예고

이제 데이터를 담는 그릇(자료구조)을 선형부터 비선형까지 다 배웠습니다. 다음 시간부터는 카테고리 D로 넘어가, 그 위에서 데이터를 다루는 알고리즘을 봅니다. 첫 주제는 정렬(sort)이에요. 뒤죽박죽인 데이터를 줄 세우는 방법인데, 버블·선택 정렬의 O(n²)를 병합·퀵 정렬의 O(n log n)으로 끌어내리는 여정입니다. 지난 시간 힙으로 "다 넣고 하나씩 빼면 정렬된다"를 잠깐 봤는데, 그 힙 정렬도 다시 만나요. 정렬이 정렬로 끝나지 않고 이진 탐색(D-3)·투 포인터(D-4)의 발판이 된다는 것까지, 다음 시간에 이어 갑니다.

과제

오늘 배운 그래프 표현을 직접 손으로 다뤄 보는 문제들입니다. 풀어 본 뒤 예시 답안과 맞춰 보세요. 각 풀이의 시간·공간 복잡도를 빅오로 적는 것도 잊지 마세요.

[기초] 가장 인기 있는 정점 찾기

무방향 그래프가 정점 수 n과 간선 목록 edges([(u, v), ...])로 주어집니다. 이 그래프에서 차수가 가장 큰 정점의 번호를 반환하는 함수 most_connected(n, edges)를 작성하세요. 차수가 같은 정점이 여럿이면 번호가 가장 작은 것을 반환합니다.

예를 들어 n=5, edges=[(0,1),(0,2),(1,2),(1,3),(2,3),(3,4)]이면 1번이 0·2·3과 이어져 차수 3으로 가장 크니 답은 1입니다. "친구가 가장 많은 사람 찾기" 같은 유형이에요. 인접 리스트를 통째로 만들 필요 없이, 간선을 훑으며 차수만 세도 됩니다. 무방향이라 간선 하나가 양 끝 정점 차수를 모두 올린다는 점을 챙기세요. 시간·공간 복잡도를 빅오로 적으세요.

[응용] 인접 행렬을 인접 리스트로

인접 행렬 matrix(V×V 2차원 리스트, matrix[u][v]가 0이 아니면 간선)가 주어질 때, 이를 인접 리스트(각 정점의 이웃 번호 목록을 담은 리스트)로 변환하는 함수 matrix_to_list(matrix)를 작성하세요.

예를 들어 4×4 행렬에서 0이 아닌 칸을 모으면 [[1,2],[0,3],[0,3],[1,2]] 같은 인접 리스트가 나옵니다. 오늘 배운 두 표현을 손으로 오가는 문제예요. 행렬을 인접 리스트로 바꿀 때 왜 O(V²)가 드는지(간선이 적어도 빈 칸까지 다 봐야 하죠), 그리고 결과 인접 리스트의 공간이 왜 O(V+E)로 줄어드는지를 빅오로 함께 적으세요.

[심화] 방향 그래프의 진입·진출 차수

방향 그래프가 정점 수 n과 간선 목록 edges(각 (u, v)는 u에서 v로 향하는 간선)로 주어집니다. 정점마다 (진입 차수, 진출 차수)를 계산해 리스트로 반환하는 함수 in_out_degree(n, edges)를 작성하세요. 진입 차수는 그 정점으로 들어오는 화살표 수, 진출 차수는 나가는 화살표 수입니다.

예를 들어 edges=[(0,1),(0,2),(1,2),(2,3)]이면 0번은 (진입 0, 진출 2), 2번은 (진입 2, 진출 1)이 됩니다. 무방향과 달리 방향 그래프는 두 차수를 따로 세야 해요. 힌트를 하나 드리면, 이 진입 차수는 나중에 위상 정렬(F-2)에서 "가장 먼저 처리할 정점(들어오는 게 없는 것)"을 고르는 열쇠가 됩니다. 순회 없이 간선만 한 번 훑으면 O(V+E)에 끝나요. 시간·공간 복잡도를 빅오로 적으세요.

생각해볼 주제

정답이 하나가 아닌 질문들입니다. 혼자 고민해도 좋고, 스터디에서 토론해도 좋아요.

1. 인접 행렬과 인접 리스트, 무엇을 보고 고를까?

오늘 두 표현의 빅오가 거울처럼 뒤집힌 걸 봤습니다. 행렬은 간선 확인 O(1)·공간 O(V²), 리스트는 공간 O(V+E)·이웃 순회 O(degree)였죠. 그렇다면 어떤 문제를 받았을 때 무엇을 고를지, 그 판단 기준을 스스로 정리해 보세요. 정점 수 제한이 얼마일 때 인접 행렬의 O(V²)가 감당되는지, 간선이 얼마나 빽빽해야 밀집이라 부를 만한지, "두 정점이 이어졌나"를 자주 물어야 하는 문제와 "한 정점의 이웃을 훑는" 문제 중 각각 어느 표현이 유리한지를 짚어 보면 좋습니다.

2. 방향 그래프로는 무엇을 표현하나?

무방향 그래프는 "서로 친구"처럼 대칭 관계를, 방향 그래프는 "팔로우"처럼 한쪽으로만 향하는 관계를 담았습니다. 방향이 꼭 필요한 관계에는 또 무엇이 있을까요? 선행 과목("A를 들어야 B를 들을 수 있다"), 작업 순서, 웹페이지 링크 같은 예를 떠올려 보세요. 그리고 [심화] 과제에서 다룬 진입 차수가 이런 방향 그래프에서 무엇을 뜻하는지 — 예컨대 "진입 차수가 0인 정점"은 어떤 특별한 위치인지 — 생각해 보면, 왜 위상 정렬이 진입 차수에서 출발하는지가 보일 거예요.

3. 트리는 그래프의 특수한 경우 — 카테고리 B·C를 돌아보며

오늘 "트리는 사이클 없이 연결된 특수한 그래프"라는 말로 문을 열었습니다. 이 한 문장에 카테고리 B와 C 전체가 담겨 있어요. 선형 자료구조(스택·큐·연결 리스트·해시)에서 비선형(트리·힙·그래프)으로 넘어온 흐름을 되짚어 보세요. 연결 리스트의 노드가 다음 하나를 가리켰다면 트리의 노드는 자식 여럿을, 그래프의 정점은 이웃을 자유롭게 가리켰죠. 이 그릇들이 각각 어떤 관계를 담기에 좋은지, 그리고 왜 자료구조를 먼저 배운 뒤에 알고리즘(정렬·탐색·탐색 알고리즘)으로 넘어가는지를 정리해 보면, 앞으로 배울 D·E·F가 왜 이 순서인지 선명해집니다.