20 — 그래프 개념과 용어

람다가 SNS 친구 관계도(여러 사람이 선으로 얽힌 그림)를 보며 "여기 점들이 선으로 막 이어져 있네?"라고 발견하고, 제네릭이 지하철 노선도를 펼쳐 보이며 "이것도 역(점)이랑 노선(선)으로 이어져!"라고 거들자, 돌핀쌤이 "점과 선으로 이어진 그 구조가 바로 그래프예요"라고 안내하는 도입

🙋‍♀️ 람다: "선생님, SNS 친구 관계도를 봤는데 사람마다 동그라미(점)가 있고 친구 사이는 선으로 이어져 있었어요. 위아래 순서도 없고요!"

🙋‍♂️ 제네릭: "지하철 노선도도 똑같아요! 역이 점이고, 역과 역을 잇는 노선이 선이잖아요."

🐬 돌핀쌤: "두 친구가 발견한 그 구조가 바로 오늘 배울 그래프예요. 점(노드)과 선(간선)으로 이어진 자료구조랍니다. 지난 시간에 배운 트리도 사실은 그래프의 한 종류예요."

🎯 오늘 완성할 코드는?

오늘 만들 건 그래프를 컴퓨터에 저장하는 가장 기본 방법, 인접 행렬이에요. 점들 사이가 연결됐는지(1)·안 됐는지(0) 를 표 한 장으로 적어 두는 방식이랍니다.

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

matrix = [
    #A  B  C  D
    [0, 1, 1, 1],  # A
    [1, 0, 0, 1],  # B
    [1, 0, 0, 0],  # C
    [1, 1, 0, 0],  # D
]
print(matrix[0][1])   # 1 (A-B 연결됨)
print(matrix[1][2])   # 0 (B-C 연결 안 됨)

실행하면 이렇게 나와요.

1
0

matrix[0][1] 은 A와 B 사이를 본 거예요. 1이 나왔으니 둘은 연결돼 있어요. matrix[1][2] 는 B와 C 사이인데 0이니까 연결 안 됨이에요.

🐬 돌핀쌤: "표 한 장이지만 그래프의 연결 정보가 전부 들어 있어요. 지금부터 이 표를 어떻게 읽는지, 그리고 그래프 용어부터 하나씩 풀어볼게요."

💡 어떻게 풀까? — 점과 선을 표로 적기

먼저 그래프가 뭔지부터 봐요. 그래프는 점들과, 그 점들을 잇는 선으로 이루어진 자료구조예요.

그래프 예시:

    A ─── B
    |   ╲ |
    C     D

정점(노드) = 점. 여기서는 A, B, C, D
간선(엣지) = 점을 잇는 선. A-B, A-C, A-D, B-D
차수 = 한 점에 붙은 선의 수. A에는 B·C·D 세 개가 붙었으니 A의 차수는 3

이 점과 선을 컴퓨터에 저장하려면 어떻게 할까요? 가장 직관적인 방법이 표(인접 행렬) 예요. 가로줄·세로줄에 점을 똑같이 적어 두고, 두 점이 만나는 칸에 연결됐으면 1, 아니면 0을 적는 거예요.

그래프:         인접 행렬:
                   A  B  C  D
A ─── B        A [ 0  1  1  1 ]
|   ╲ |        B [ 1  0  0  1 ]
C     D        C [ 1  0  0  0 ]
               D [ 1  1  0  0 ]

1 = 연결됨, 0 = 연결 안 됨

위 SNS 친구 관계도, 지하철 노선도도 이렇게 점과 선으로 그린 다음 표로 옮길 수 있어요. 맨 위 🎯 코드가 바로 이 표를 그대로 옮겨 적은 거랍니다.

🙋‍♀️ 람다: "표 A행 B열을 보면 둘이 친구인지 한 번에 알 수 있네요!"

🔍 코드 한 줄씩 뜯어보기

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

① 표(2차원 리스트)를 만들어요

matrix = [
    #A  B  C  D
    [0, 1, 1, 1],  # A
    [1, 0, 0, 1],  # B
    [1, 0, 0, 0],  # C
    [1, 1, 0, 0],  # D
]

리스트 안에 리스트가 들어 있는 모양이에요. 바깥 리스트의 한 칸(matrix[0])이 표의 한 줄(行)이고, 그 안의 값들이 각 열(列)이에요. 줄과 칸 모두 순서대로 A=0, B=1, C=2, D=3 번이에요.

💡 맨 윗줄 [0, 1, 1, 1] 은 A의 줄이에요. "A는 A와 연결 안 됨(0, 자기 자신), B와 연결(1), C와 연결(1), D와 연결(1)"이라는 뜻이지요. 그래서 A의 차수가 3이에요.

② 두 점이 연결됐는지 확인해요 — `matrix[줄][칸]`

print(matrix[0][1])   # 1 (A-B 연결됨)

matrix[0][1] 은 0번 줄(A) 의 1번 칸(B) 을 꺼낸 거예요. 값이 1이니 A와 B는 연결돼 있어요.

💡 번호 헷갈리지 않기: A=0, B=1, C=2, D=3 이에요. 그래서 "A와 B 연결?"은 matrix[0][1], "B와 C 연결?"은 matrix[1][2] 처럼 앞 점 번호·뒤 점 번호 순으로 적어요.

③ 연결 안 된 경우는 0이 나와요

print(matrix[1][2])   # 0 (B-C 연결 안 됨)

matrix[1][2] 는 1번 줄(B) 의 2번 칸(C) 이에요. 값이 0이니 B와 C는 연결 안 됨이에요. 표만 보면 두 점이 친구인지 아닌지를 딱 한 번에(O(1)) 알 수 있어요. 이게 인접 행렬의 가장 큰 장점이에요.

④ 표는 대각선을 기준으로 좌우가 똑같아요

방향이 없는 그래프(친구 관계처럼 서로 연결)는 "A-B 연결"이면 "B-A 연결"도 같은 말이에요. 그래서 표가 대각선 기준으로 대칭이 돼요.

   A  B  C  D
A [0  1  1  1]
B [1  0  0  1]
C [1  0  0  0]
D [1  1  0  0]
   ↑ matrix[0][1] = 1 (A→B)
     matrix[1][0] = 1 (B→A)  ← 같은 값!

🙋‍♂️ 제네릭: "A행 B열이 1이면 B행 A열도 1이네요. 거울처럼 똑같아요!"

✍️ 직접 완성해보기

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

matrix = [
    #A  B  C  D
    [0, 1, 1, 1],  # A
    [1, 0, 0, 1],  # B
    [1, 0, 0, 0],  # C
    [1, 1, 0, 0],  # D
]
print(matrix[0][___])   # A-B 연결 확인 → 1
print(matrix[___][2])   # B-C 연결 확인 → 0

🐬 돌핀쌤: "A=0, B=1, C=2, D=3 번이라는 것만 기억하면 빈칸이 보일 거예요. 막히면 위 '코드 한 줄씩 뜯어보기'로 다시 올라가서 확인해요. 다 채웠으면 맨 위 🎯 완성 코드와 비교해보세요. 정답을 외우는 게 아니라 왜 그런지 떠올리는 게 진짜 공부예요."

📌 오늘 배운 것

개념	설명
그래프	정점(점, 노드)과 간선(선, 엣지)으로 이어진 자료구조
차수(Degree)	한 정점에 붙은 간선의 수 (A의 차수 = 3)
인접 행렬	점들을 가로·세로에 적고, 연결되면 1·아니면 0을 적은 V×V 표
연결 확인	`matrix[앞점][뒤점]` → 1이면 연결, 0이면 연결 안 됨 (O(1))
트리와 관계	트리는 사이클 없고 루트 하나인 그래프, 즉 그래프의 특수한 경우

🐬 돌핀쌤: "점과 선, 그리고 그걸 표로 적는 인접 행렬! 이 세 가지면 그래프의 첫걸음은 끝이에요. 잘했어요! 👏"

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

여기까지가 오늘의 필수 내용이에요. 아래는 여유 있을 때 살펴보는 내용이에요. 외울 필요는 없어요.

인접 리스트 — 표 대신, 점마다 "이웃 목록"만 적어 두는 방법이에요. {'A': ['B', 'C', 'D'], ...} 처럼 딕셔너리로 담아요. 점은 많은데 선이 적을 때 메모리를 훨씬 아낄 수 있어요. 다음 21차시에서 직접 구현하니 지금은 "이런 방법도 있구나" 정도만 알아 두면 돼요.
무방향 vs 방향 그래프 — 친구 관계는 서로라서 양쪽을 다 연결(무방향)하고, 팔로우는 한쪽만 연결(방향)해요. → 예제로 연습
가중치 그래프 — 간선에 거리·시간·요금 같은 비용을 붙인 그래프예요. 네비게이션의 "최단 경로 찾기"가 여기에 해당해요. → 예제로 연습
dict로 그래프 만들기 — if 노드 not in graph: graph[노드] = [] 로 빈 목록을 만들고 append 로 이웃을 더해 그래프를 직접 쌓아요. → 예제로 연습

참고 — 인접 행렬 vs 인접 리스트, 무엇을 쓸까?

비교 항목	인접 행렬	인접 리스트
메모리	O(V²) — 항상 V×V 표	O(V + E) — 실제 간선만큼
연결 여부 확인	O(1) — `matrix[u][v]`	O(차수) — 이웃 목록 훑기
언제 유리한가	점 수 작고 선 많을 때	점 수 많고 선 적을 때

정점 1000개, 간선 2000개라면?

인접 행렬: 1000 × 1000 = 1,000,000칸 필요
인접 리스트: 1000 + 2000 = 3,000칸만 필요  ← 훨씬 효율적!

선이 적은(드문드문 연결된) 그래프에서는 인접 리스트가 메모리를 크게 아껴요. 그래서 BFS·DFS 같은 탐색에서는 인접 리스트를 많이 쓴답니다(21차시에서 이어서 배워요).

20 — 그래프 개념과 용어

📃 해결할 문제

💻 예제 입력 1

🖨️ 예제 출력 1