21 — 인접 리스트 구현

람다가 반 친구 관계를 표로 정리하다가 "민준이의 친구는 서연·지호, 서연이의 친구는 민준·지호·유나…"처럼 각자가 자기만의 친구 목록(이웃 리스트)을 가진 걸 발견하고, 제네릭이 "그럼 사람마다 친구 목록을 하나씩 들고 있으면 그래프가 되겠네!"라고 거들자, 돌핀쌤이 "그렇게 각 노드가 이웃 리스트를 들고 있는 게 바로 인접 리스트예요"라고 안내하는 도입

🙋‍♀️ 람다: "선생님, 우리 반 친구 관계를 표로 적어 봤는데요. 민준이의 친구는 서연·지호, 서연이의 친구는 민준·지호·유나… 어? 사람마다 자기만의 친구 목록을 하나씩 들고 있는 것 같아요!"

🐬 돌핀쌤: "정확해요! 각 친구가 '나와 연결된 이웃들의 리스트'를 하나씩 들고 있죠. 이렇게 노드마다 이웃 리스트를 들고 있는 표현 방법이 바로 오늘 만들 인접 리스트예요. 지난 시간에 눈으로 본 그래프를, 오늘은 딕셔너리로 컴퓨터 안에 담아 볼게요."

🎯 오늘 완성할 코드는?

오늘 우리가 만들 건 인접 리스트로 표현한 그래프예요. 노드(친구)를 넣고 간선(친구 관계)을 이으면, 각 노드의 이웃 목록을 꺼내고 두 노드가 연결됐는지 확인할 수 있는 작은 그래프 도구랍니다.

먼저 완성된 모습부터 볼게요. 지금은 이해 안 돼도 괜찮아요. 아래에서 한 줄씩 천천히 뜯어볼 거예요.

# 인접 리스트 — 기본 버전 (그래프 만들고 이웃/연결 확인)
class Graph:
    def __init__(self):
        self.adj = {}                # 노드 → 이웃 리스트
    def add_vertex(self, v):
        if v not in self.adj:
            self.adj[v] = []         # 새 노드는 빈 리스트로 시작
    def add_edge(self, v1, v2):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.adj[v1].append(v2)
        self.adj[v2].append(v1)      # 무방향: 양쪽에 추가
    def neighbors(self, v):
        return self.adj.get(v, [])   # v의 이웃 목록
    def has_edge(self, v1, v2):
        return v2 in self.adj.get(v1, [])   # v1-v2 직접 연결?
    def print_graph(self):
        for vertex, ns in self.adj.items():
            print(f"  {vertex}: {ns}")

g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')
g.add_edge('D', 'E')
print("=== 그래프 구조 ===")
g.print_graph()
print()
print("A의 이웃:", g.neighbors('A'))
print("D의 이웃:", g.neighbors('D'))
print()
print("A-B 연결?", g.has_edge('A', 'B'))
print("A-E 연결?", g.has_edge('A', 'E'))
print("D-E 연결?", g.has_edge('D', 'E'))

실행하면 이렇게 나와요.

=== 그래프 구조 ===
  A: ['B', 'C']
  B: ['A', 'D']
  C: ['A', 'D']
  D: ['B', 'C', 'E']
  E: ['D']

A의 이웃: ['B', 'C']
D의 이웃: ['B', 'C', 'E']

A-B 연결? True
A-E 연결? False
D-E 연결? True

점과 선으로 그려야 할 그래프가, 노드 이름 → 이웃 목록 형태의 딕셔너리로 깔끔하게 담겼죠?

🐬 돌핀쌤: "메서드가 여러 개라 길어 보이지만, 핵심은 딱 두 가지예요. 노드마다 이웃 리스트 하나씩 들고 있기, 그리고 그 리스트를 꺼내 보기. 지금부터 이 코드가 어떻게 그래프를 담는지 한 줄씩 풀어볼게요."

💡 어떻게 풀까? — 사람마다 친구 목록 하나씩

람다가 발견한 걸 그림으로 볼게요. 네모난 그래프 하나를 떠올려 봐요.

그래프:           인접 리스트(딕셔너리):
A ── B            {
|    |              'A': ['B', 'C'],
C ── D              'B': ['A', 'D'],
                    'C': ['A', 'D'],
                    'D': ['B', 'C']
                  }

각 노드가 "나와 연결된 이웃들의 목록(리스트)" 을 하나씩 들고 있어요. A의 이웃은 B·C, B의 이웃은 A·D… 이렇게요. 이 "노드 → 이웃 리스트" 묶음을 파이썬의 딕셔너리에 담은 게 바로 인접 리스트예요.

🙋‍♂️ 제네릭: "친구 관계는 서로니까 A의 목록에 B를 넣으면 B의 목록에도 A를 넣어야겠네요. 양쪽에!"

람다가 표에 적은 "사람마다 친구 목록"이, 맨 위 코드의 self.adj 딕셔너리 그대로예요. 사람 이름 대신 A, B, C 같은 글자가 들어가도 똑같답니다.

🔍 코드 한 줄씩 뜯어보기

이제 맨 위에서 본 완성 코드를 한 줄씩 볼게요.

① 빈 인접 리스트 만들기

def __init__(self):
    self.adj = {}                # 노드 → 이웃 리스트

Graph를 만들면 self.adj라는 빈 딕셔너리가 하나 생겨요. 여기에 "노드 → 이웃 리스트"를 차곡차곡 담을 거예요.

② 노드 추가하기

def add_vertex(self, v):
    if v not in self.adj:
        self.adj[v] = []         # 새 노드는 빈 리스트로 시작

새 노드 v가 아직 딕셔너리에 없으면, 그 노드를 빈 리스트 [] 와 함께 넣어요. 빈 리스트로 시작하는 이유는, 이웃이 생길 때마다 여기에 하나씩 append 할 거니까요.

💡 if v not in self.adj: 가 없으면 어떻게 될까요? 이미 있는 노드를 다시 넣을 때 self.adj[v] = [] 로 이웃 목록이 통째로 지워져요. 그래서 "없을 때만 새로 넣기" 조건이 꼭 필요해요.

③ 간선(연결) 추가하기 — 양쪽에

def add_edge(self, v1, v2):
    self.add_vertex(v1)
    self.add_vertex(v2)
    self.adj[v1].append(v2)
    self.adj[v2].append(v1)      # 무방향: 양쪽에 추가

두 노드를 잇는 부분이에요. 먼저 add_vertex로 두 노드가 딕셔너리에 있는지 챙기고(없으면 자동으로 만들어 줘요), 그다음 서로의 이웃 목록에 상대를 넣어요.

친구 관계는 한쪽만 친구일 수 없죠? 그래서 adj[v1]에 v2를 넣고, adj[v2]에도 v1을 넣어요. 이렇게 양쪽에 넣는 그래프를 무방향 그래프라고 불러요.

add_edge('A', 'B') 하면:
  A의 목록: [] → ['B']
  B의 목록: [] → ['A']     ← 양쪽 다!

④ 이웃 목록 꺼내기

def neighbors(self, v):
    return self.adj.get(v, [])   # v의 이웃 목록

노드 v의 이웃 목록을 돌려줘요. self.adj[v] 가 아니라 self.adj.get(v, []) 를 쓴 게 포인트예요. 딕셔너리에 없는 노드를 adj[v]로 꺼내면 에러(KeyError) 가 나지만, get(v, []) 는 없을 때 빈 리스트 [] 를 돌려줘서 안전해요.

⑤ 직접 연결됐는지 확인하기

def has_edge(self, v1, v2):
    return v2 in self.adj.get(v1, [])   # v1-v2 직접 연결?

v1의 이웃 목록 안에 v2가 들어 있는지(in)를 확인해요. 있으면 True(바로 연결됨), 없으면 False예요.

💡 has_edge는 바로 옆에 붙어 있는지만 확인해요. 맨 위 코드에서 A-E 연결? 이 False인 건, A와 E가 직접 이어져 있지 않기 때문이에요. 사실 A → B → D → E 처럼 여러 칸을 거치면 갈 수는 있지만, 그 "길 찾기"는 이웃을 한 칸씩 따라가며 넓혀야 하는 더 깊은 내용이에요. 오늘은 직접 연결까지만 확인해요.

⑥ 전체 모습 보기

def print_graph(self):
    for vertex, ns in self.adj.items():
        print(f"  {vertex}: {ns}")

딕셔너리를 돌면서 노드 하나하나와 그 이웃 목록을 보기 좋게 출력해요. 그래서 실행하면 A: ['B', 'C'] 처럼 그래프 전체가 한눈에 보이죠.

🙋‍♀️ 람다: "노드를 키로, 이웃을 리스트로 넣고 → 연결할 땐 양쪽에 넣고 → 이웃은 그냥 꺼내 보고! 제가 표에 적은 게 그대로 코드가 됐어요."

✍️ 직접 완성해보기

이제 빈칸을 채워 직접 완성해봐요. 위에서 본 그대로예요.

# ─────────────────────────────────────────────────────────
# 인접 리스트 — 빈칸(___)을 채워 직접 완성해 보세요!
#  • 수업의 '직접 완성해보기'에서 본 그대로예요.
#  • 막히면 수업의 '코드 한 줄씩 뜯어보기'로 돌아가 확인하세요.
# ─────────────────────────────────────────────────────────

class Graph:
    def __init__(self):
        self.adj = {}                # 노드 → 이웃 리스트
    def add_vertex(self, v):
        if v not in self.adj:
            self.adj[v] = ___        # 새 노드는 빈 리스트로 시작
    def add_edge(self, v1, v2):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.adj[v1].___(v2)         # 이웃 목록에 추가
        self.adj[v2].append(v1)      # 무방향: 양쪽에 추가
    def neighbors(self, v):
        return self.adj.get(v, [])   # v의 이웃 목록
    def has_edge(self, v1, v2):
        return v2 ___ self.adj.get(v1, [])   # v1-v2 직접 연결?
    def print_graph(self):
        for vertex, ns in self.adj.items():
            print(f"  {vertex}: {ns}")

g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')
g.add_edge('D', 'E')
print("=== 그래프 구조 ===")
g.print_graph()
print()
print("A의 이웃:", g.neighbors('A'))
print("D의 이웃:", g.neighbors('D'))
print()
print("A-B 연결?", g.has_edge('A', 'B'))
print("A-E 연결?", g.has_edge('A', 'E'))
print("D-E 연결?", g.has_edge('D', 'E'))

🐬 돌핀쌤: "막히면 위 '코드 한 줄씩 뜯어보기'로 다시 올라가서 확인해요. 다 채웠으면 맨 위 🎯 완성 코드와 비교해보세요. 정답을 외우는 게 아니라 왜 그런지 떠올리는 게 진짜 공부예요."

📌 오늘 배운 것

개념	설명
인접 리스트	노드를 키로, 이웃들의 리스트를 값으로 딕셔너리에 저장
노드 추가	`self.adj[v] = []` — 새 노드는 빈 리스트로 시작(`if not in`으로 덮어쓰기 방지)
간선 추가	무방향은 `adj[v1]`·`adj[v2]` 양쪽에 서로를 `append`
이웃 조회	`self.adj.get(v, [])` — 없는 노드도 빈 리스트로 안전하게
직접 연결 확인	`v2 in adj[v1]` — 바로 옆에 있는지만 확인

🐬 돌핀쌤: "노드마다 이웃 리스트 하나씩, 연결은 양쪽에, 이웃은 꺼내 보기! 이 세 박자면 어떤 그래프든 인접 리스트로 담을 수 있어요. 잘했어요! 👏"

▸ 더 해보기 — 여기서부터는 선택!

여기까지가 오늘의 필수 내용이에요. 아래는 여유 있을 때 도전하는 내용이고, 예제 문제로 직접 풀어볼 수 있어요. 외울 필요는 없어요. 전부 오늘 만든 Graph 클래스 위에 메서드를 조금 더 붙인 것뿐이에요.

방향 그래프 만들기 — 팔로우처럼 한쪽으로만 가는 관계는 add_directed_edge로 adj[v1]에만 append 해요. add_edge(양쪽)와 비교하면 무방향·방향의 차이가 한눈에 보여요. → 예제로 연습
정점/간선 개수 세기 — vertex_count는 len(self.adj)로 노드 수를, edge_count는 모든 이웃 수를 더한 뒤 // 2(양쪽 저장이라 2로 나눔)로 간선 수를 구해요. → 예제로 연습
친구 관계 그래프 만들기 — A, B 대신 "민준", "서연" 같은 이름을 넣어도 똑같이 동작해요. 우리 반 친구 관계를 직접 인접 리스트로 만들어 봐요. → 예제로 연습
간선 삭제하기 — remove_edge로 두 노드의 이웃 목록에서 서로를 remove 하면 연결이 끊겨요. → 예제로 연습

자주 하는 실수 세 가지

무방향인데 한쪽만 추가 — adj[v1]에만 넣고 adj[v2]를 깜빡하면 무방향이 아니라 방향 그래프가 돼요. 무방향은 꼭 양쪽에 넣어요.
같은 간선 두 번 추가 — add_edge('A','B') 를 두 번 하면 ['B', 'B'] 처럼 중복돼요. 막으려면 if v2 not in self.adj[v1]: 로 추가 전에 확인해요.
없는 노드를 adj[v]로 조회 — 딕셔너리에 없는 노드를 adj[v]로 꺼내면 에러가 나요. 항상 adj.get(v, [])(또는 neighbors)로 안전하게 꺼내세요.

21 — 인접 리스트 구현

📃 해결할 문제

💻 예제 입력 1

🖨️ 예제 출력 1