14강 / 20강

그래프 — 점과 선으로 그린 관계

친구 관계, 지하철 노선도, 인터넷 그 자체

트리에는 규칙이 있었습니다 — 부모는 하나, 순환은 없음. 이 규칙을 전부 없애면 어떻게 될까요? 아무 점이나 아무 점과 이어질 수 있는 구조, 그게 그래프(graph)입니다.

SNS 친구 관계 — 나와 친구, 친구의 친구
지하철 노선도 — 역과 역 사이의 연결
내비게이션 — 교차로와 도로
인터넷 — 웹페이지와 링크

용어	뜻
정점 (vertex, node)	점 하나 — 사람, 역, 도시
간선 (edge)	점을 잇는 선 — 친구 관계, 노선
방향 그래프	화살표가 있음 — 인스타 팔로우(내가 팔로우해도 상대는 아닐 수 있음)
무방향 그래프	화살표 없음 — 페이스북 친구(양쪽 다 친구)
가중치	선에 붙은 숫자 — 거리, 시간, 요금

고등학생점과 선으로 그린 관계

10강의 트리는 계층을 담았습니다. 그런데 세상에는 계층이 아닌 관계가 더 많아요.

그래프 = 점(정점)과 선(간선)

트리와 무엇이 다른가

	트리	그래프
부모	하나	여럿 가능
고리(순환)	없다	있을 수 있다
시작점	루트	정해진 게 없다

제한을 풀면 훨씬 많은 것을 담을 수 있다

일상의 그래프

것	점	선
친구 관계	사람	친구다
지하철	역	노선
인터넷	컴퓨터	연결
웹	페이지	링크
도로	교차로	길

"무엇이 무엇과 이어져 있다" 는 전부 그래프다

방향이 있냐 없냐

종류	예
무향	친구 관계 — 서로
유향	팔로우 · 링크 — 한쪽만

방향이 있으면 돌아올 수 없는 길이 생긴다

그래프를 코드로 담는 두 가지 방법

📇 인접 리스트

딕셔너리 + 리스트
각 점이 이웃 목록을 들고 있음
선이 적을 때 메모리 절약 ✅
대부분의 실제 그래프가 이 경우

🔢 인접 행렬

2차원 리스트
[ㄱ][ㄴ] 이 1이면 연결됨
"둘이 이어졌나?"를 즉시 확인 ✅
점이 많으면 메모리 폭발 ❌

그래프는 특별한 문법이 아니라 딕셔너리 + 리스트입니다.

Python 브라우저에서 실행

# 인접 리스트 — 딕셔너리 하나면 됩니다
친구 = {
    "민준": ["서연", "지호"],
    "서연": ["민준", "하윤"],
    "지호": ["민준", "하윤", "예준"],
    "하윤": ["서연", "지호"],
    "예준": ["지호"],
}

for 사람, 이웃 in 친구.items():
    print(f"{사람:4} — 친구 {len(이웃)}명: {', '.join(이웃)}")

print()
print("민준과 하윤은 친구인가?", "하윤" in 친구["민준"])
print("민준과 하윤의 공통 친구:", set(친구["민준"]) & set(친구["하윤"]))

고등학생그래프를 코드로 담는 두 방법

점과 선을 어떻게 저장할까요?

방법	모양
인접 리스트	각 점마다 이웃 목록
인접 행렬	표 — 이어졌으면 1

인접 리스트 (딕셔너리로)

이웃 = {
  "A": ["B", "C"],
  "B": ["A", "D"],
  "C": ["A"],
}

5강의 딕셔너리가 그대로 그래프가 된다

비교

	인접 리스트	인접 행렬
메모리	선의 개수만큼	점² ⚠
"A와 B가 이어졌나"	목록을 훑는다	즉시 ✔
"A의 이웃 전부"	즉시 ✔	한 줄을 다 본다

선이 적으면 리스트, 선이 빽빽하면 행렬

현실은 대개 성깁니다

친구 관계를 생각해 보세요. 100만 명 중 내 친구는 300명 정도죠.

방법	메모리
인접 행렬	100만² = 1조 칸 ⚠
인접 리스트	3억 칸 ✔

현실의 그래프는 대부분 성글다 — 그래서 리스트를 쓴다

비유 — 주소록과 출석표

	비유
인접 리스트	내 연락처 목록 — 아는 사람만
인접 행렬	전교생 × 전교생 표 — 대부분 빈칸

5강의 희소 표현 이야기와 같은 판단

🎮 그래프 실험실

점을 클릭해 선을 이어 보세요. 인접 리스트와 인접 행렬이 동시에 갱신되는 걸 볼 수 있습니다. 점이 늘어날 때 행렬 칸이 얼마나 빠르게 불어나는지도 확인해 보세요.

같은 그래프, 두 가지 모습. 행렬은 점 개수의 제곱만큼 자랍니다.

Python 브라우저에서 실행

이름들 = ["민준", "서연", "지호", "하윤", "예준"]
친구 = {
    "민준": ["서연", "지호"], "서연": ["민준", "하윤"],
    "지호": ["민준", "하윤", "예준"], "하윤": ["서연", "지호"], "예준": ["지호"],
}

# 같은 그래프를 인접 행렬로
ㄴ = len(이름들)
행렬 = [[0] * ㄴ for _ in range(ㄴ)]
for ㅇ, ㄱ in enumerate(이름들):
    for ㄴ2 in 친구[ㄱ]:
        행렬[ㅇ][이름들.index(ㄴ2)] = 1

print("      " + " ".join(f"{ㅇ:>4}" for ㅇ in 이름들))
for ㅇ, 줄 in enumerate(행렬):
    print(f"{이름들[ㅇ]:>4}  " + " ".join(f"{ㄱ:>4}" for ㄱ in 줄))

print()
print(f"점 {ㄴ}개 → 행렬 칸 {ㄴ*ㄴ}개, 그중 실제로 쓰는 칸은 {sum(map(sum, 행렬))}개")
print(f"점이 1000개라면 → 칸 {1000*1000:,}개가 필요합니다 😱")

고등학생트리도 그래프입니다

note 의 이 문장이 관계를 정리해 줍니다.

트리 = 고리가 없고 이어져 있는 그래프

포함 관계

구조	제한
그래프	없다
트리	고리가 없다 · 하나로 이어짐
이진 트리	자식이 둘 이하
BST	왼 < 나 < 오
연결 리스트	자식이 하나

아래로 갈수록 제한이 늘고 대신 할 수 있는 게 명확해진다

이 강의 전체가 이 사다리였습니다

강	화살표
8강	다음 하나
10강	자식 여럿 · 고리 없음
14강	아무 데나

제한을 하나씩 풀어 온 같은 발상이다

그런데 고리가 생기면 문제가 하나

트리는 재귀로 훑으면 끝났습니다. 그래프는 돌고 돌 수 있어요.

구조	순회
트리	재귀 — 끝난다
그래프	무한 루프 위험 ⚠

그래서 "본 곳" 표시가 필요하다 — 15강

비유 — 미로와 나무 지도

	나무 (트리)	미로 (그래프)
돌아오나	안 온다	돌아올 수 있다
필요한 것	—	실 · 표시

테세우스의 실 — 지나온 곳을 표시해야 빠져나온다

지하철 노선도를 그래프로. 마지막 부분이 15강 BFS입니다.

Python 브라우저에서 실행

# 가중치 그래프 — 선마다 숫자가 붙습니다
지하철 = {
    "서울역": [("시청", 2), ("남영", 2)],
    "시청":   [("서울역", 2), ("종각", 2)],
    "종각":   [("시청", 2), ("종로3가", 2)],
    "남영":   [("서울역", 2), ("용산", 3)],
    "용산":   [("남영", 3)],
    "종로3가": [("종각", 2)],
}

def 이웃보기(역):
    for 다음, 분 in 지하철[역]:
        print(f"  {역} → {다음} : {분}분")

이웃보기("서울역")
print()

# 서울역에서 각 역까지 '몇 정거장'인지 — 다음 강의 BFS 미리보기
from collections import deque
거리 = {"서울역": 0}
ㄷ = deque(["서울역"])
while ㄷ:
    지금 = ㄷ.popleft()
    for 다음, _ in 지하철[지금]:
        if 다음 not in 거리:
            거리[다음] = 거리[지금] + 1
            ㄷ.append(다음)

for 역, ㄱ in sorted(거리.items(), key=lambda ㅍ: ㅍ[1]):
    print(f"서울역 → {역:6} : {ㄱ} 정거장")

고등학생가중치와 방향 — 현실을 담기

실제 문제에서는 선에 숫자가 붙습니다.

가중치 = 그 선을 지나는 비용

그래프	가중치
지도	거리 · 시간
지하철	소요 시간 · 요금
네트워크	지연 시간

가중치가 있으면 "가장 짧은 길" 을 물을 수 있다

그런데 문제가 달라집니다

가중치	최단 경로
없다 (전부 1)	BFS 로 충분 (15강)
있다	다익스트라 — 힙이 필요 (12강)

가중치가 있으면 "가까운 순서" 가 "적게 거친 순서" 와 다르다

비유 — 환승 횟수와 소요 시간

경로	환승	시간
A	1번	50분
B	3번	30분

"적게 갈아타는 길" 과 "빠른 길" 은 다르다

BFS 는 환승 횟수를 최소화하고 다익스트라는 시간을 최소화합니다.

방향이 있으면 또 달라집니다

예	주의할 점
일방통행	A→B 는 되고 B→A 는 안 된다
선행 과목	순서가 있다 — 위상 정렬
의존 관계	고리가 생기면 불가능하다

"A 를 하려면 B 가, B 를 하려면 A 가" — 순환 의존은 풀 수 없다

🤔 확인 문제

트리와 그래프의 관계로 옳은 것은?

🤔 확인 문제

정점이 1000개인데 간선은 2000개뿐인 그래프. 알맞은 표현은?

🤔 확인 문제

인스타그램 팔로우 관계를 그래프로 표현한다면?