그래프를 손으로 따라가는 문제 다섯 개다. 답을 펼치기 전에 종이에 먼저 써 본다. 탐색 문제는 “이웃을 보는 순서”가 답을 바꾸므로 문제마다 인접 리스트를 적어 두었다.
p1 · 너비 우선 탐색과 큐
점 1 ~ 11인 그래프의 인접 리스트가 다음과 같다. 이웃은 적힌 순서대로 본다.
1: 2, 4 5: 2, 9, 7, 3 9: 5, 6, 8
2: 1, 5, 3, 6 6: 2, 4, 9, 7 10: 11
3: 2, 5 7: 5, 6 11: 10
4: 1, 6 8: 9
1에서 너비 우선 탐색을 한다. (가) 방문 순서, (나) 점 하나를 큐에서 꺼내고 그 이웃을 넣은 직후의 큐를 차례로, (다) 새 점에 처음 닿을 때 쓴 간선들(너비 우선 신장 트리)을 쓰라. (라) 이 탐색에서 인접 행렬이면 행렬의 칸을 몇 개 보고, 인접 리스트면 리스트의 원소를 몇 개 보는가?
사용 개념: 너비 우선 탐색(BFS), 연결 인접 리스트와 배열 인접 리스트
풀이 전략
큐를 종이에 한 줄로 그려 놓고, 맨 앞을 지우고 뒤에 붙이기만 되풀이한다. 점을 큐에 넣는 순간 방문 표시를 해야 같은 점이 두 번 들어가지 않는다. 처음 닿게 해 준 간선에 동그라미를 치면 그것이 신장 트리다.
풀이
(가) 1, 2, 4, 5, 3, 6, 9, 7, 8.
(나) 처음 큐는 [1]이다.
| 꺼낸 점 | 새로 넣은 점 | 꺼내고 넣은 뒤의 큐 |
|---|---|---|
| 1 | 2, 4 | 2 4 |
| 2 | 5, 3, 6 | 4 5 3 6 |
| 4 | 없음(1, 6은 이미 방문) | 5 3 6 |
| 5 | 9, 7 | 3 6 9 7 |
| 3 | 없음 | 6 9 7 |
| 6 | 없음 | 9 7 |
| 9 | 8 | 7 8 |
| 7 | 없음 | 8 |
| 8 | 없음 | (빔) |
큐가 비어 끝난다. 10과 11은 1에서 닿지 않아 방문하지 않는다.
(다) 1–2, 1–4, 2–5, 2–3, 2–6, 5–9, 5–7, 9–8의 여덟 개. 방문한 점이 9개라 간선은 \(9 - 1 = 8\)개다.
(라) 큐에서 꺼낸 점이 9개다. 인접 행렬이면 꺼낼 때마다 한 줄 11칸을 다 보니 \(9 \times 11 = 99\)칸이다. 인접 리스트면 꺼낸 점의 이웃 수만큼만 본다. \(2 + 4 + 2 + 2 + 4 + 4 + 2 + 1 + 3 = 24\)개다. “인접 행렬이면 시간이 \(O(mn)\)“이라는 말이 앞의 계산이다. 여기서 \(m\)은 탐색한 덩어리의 점 수, \(n\)은 전체 점 수다.
p2 · 깊이 우선 신장 트리
p1의 그래프에서 점 10, 11을 뺀 그래프(점 1 ~ 9)를 1에서 깊이 우선 탐색한다. 이웃은 p1의 인접 리스트 순서대로 본다. (가) 방문 순서와 깊이 우선 신장 트리의 간선을 쓰라. (나) p1의 너비 우선 신장 트리와 같은가? 두 나무에서 뿌리 1부터 가장 먼 점까지의 간선 수를 견줘라.
사용 개념: 깊이 우선 탐색(DFS)
풀이 전략
지금 점의 이웃 목록에서 아직 안 간 첫 점으로 바로 들어간다. 더 갈 곳이 없으면 온 길을 한 칸 되돌아가 그 점의 목록을 이어서 본다. 들어갈 때 쓴 간선이 신장 트리다.
풀이
(가) 1 → 2(1의 첫 이웃) → 5(2의 목록에서 1은 방문, 다음이 5) → 9 → 6(9의 목록에서 5는 방문, 다음이 6) → 4(6의 목록에서 2는 방문, 다음이 4). 4에서 갈 곳이 없어 6으로 돌아가 7로 들어간다. 7에서 6, 9로 되돌아가 8로 들어간다. 다시 5까지 되돌아가 3으로 들어간다. 방문 순서는 1, 2, 5, 9, 6, 4, 7, 8, 3이다. 신장 트리의 간선은 1–2, 2–5, 5–9, 9–6, 6–4, 6–7, 9–8, 5–3이다.
(나) 다르다. 두 나무가 함께 가진 간선은 1–2, 2–5, 5–9, 9–8의 넷뿐이다. 깊이 우선 트리는 1 → 2 → 5 → 9 → 6 → 4로 간선 5개까지 내려가고, 너비 우선 트리는 가장 먼 8까지 간선 4개다. 너비 우선 트리에서 뿌리부터의 간선 수는 그 점까지의 가장 짧은 걸음 수다.
p3 · 신장 트리의 비용
점 1 ~ 11, 간선과 비용이 다음과 같은 그래프가 있다.
1–2: 4 1–4: 2 2–5: 8 3–5: 6 4–6: 5 5–6: 2 5–7: 6
6–7: 7 5–9: 4 8–9: 4 8–11: 5 9–11: 8 10–11: 3
(가) 간선 1–2, 1–4, 2–5, 4–6, 3–5, 6–7, 5–9, 8–9, 9–11, 10–11로 된 신장 트리의 비용은? (나) 크루스칼의 방법으로 최소 비용 신장 트리를 구하라. 버리는 간선과 비용 합을 쓰라. 비용이 같은 간선은 위에 적힌 순서대로 본다.
사용 개념: 최소 신장 트리
풀이 전략
(가)는 더하기만 하면 된다. 간선이 \(n - 1 = 10\)개인지 먼저 센다. (나)는 간선을 비용 순으로 다시 적고, 위에서부터 “두 끝이 이미 이어졌나”를 본다. 이어진 점 묶음을 옆에 적어 가면 틀리지 않는다.
풀이
(가) \(4 + 2 + 8 + 5 + 6 + 7 + 4 + 4 + 8 + 3 = 51\).
(나) 비용 순서: 1–4(2), 5–6(2), 10–11(3), 1–2(4), 5–9(4), 8–9(4), 4–6(5), 8–11(5), 3–5(6), 5–7(6), 6–7(7), 2–5(8), 9–11(8).
- 1–4, 5–6, 10–11, 1–2, 5–9, 8–9를 차례로 고른다. 묶음은 {1, 2, 4}, {5, 6, 8, 9}, {10, 11}, {3}, {7}.
- 4–6(5)을 골라 {1, 2, 4, 5, 6, 8, 9}. 8–11(5)을 골라 10, 11이 붙는다. 3–5(6), 5–7(6)을 골라 모든 점이 이어진다.
- 6–7(7), 2–5(8), 9–11(8)은 두 끝이 이미 이어져 있어 버린다.
고른 간선 10개의 합은 \(2 + 2 + 3 + 4 + 4 + 4 + 5 + 5 + 6 + 6 = 41\)이다. (가)의 나무보다 10이 싸다.
p4 · 세 가지 고르기 전략
점 1 ~ 8, 간선과 비용이 다음과 같은 그래프가 있다.
1–2: 2 1–3: 8 2–3: 7 2–4: 9 3–4: 4
3–5: 10 3–6: 12 5–6: 6 5–7: 14 7–8: 3
(가) 크루스칼의 방법이 간선을 보는 순서와, 간선마다 고르는지 버리는지를 쓰라. (나) 5에서 시작하는 프림의 방법이 간선을 붙이는 순서를 쓰라. (다) 솔린의 방법이 바퀴마다 넣는 간선을 쓰라. 세 방법의 비용 합은?
풀이 전략
세 방법은 “지금 고를 수 있는 간선 가운데 가장 싼 것”을 고른다는 점이 같고, “고를 수 있는 간선”의 범위가 다르다. 크루스칼은 전체, 프림은 지금 나무에 한쪽 끝만 붙은 간선, 솔린은 덩어리마다 자기에게서 나가는 간선이다.
풀이
(가) 1–2(2) 고름, 7–8(3) 고름, 3–4(4) 고름, 5–6(6) 고름, 2–3(7) 고름, 1–3(8) 버림(1과 3이 이미 이어짐), 2–4(9) 버림, 3–5(10) 고름, 3–6(12) 버림, 5–7(14) 고름. 일곱 개를 골랐다.
(나) 5–6(6), 3–5(10), 3–4(4), 2–3(7), 1–2(2), 5–7(14), 7–8(3). 처음에 5에 붙은 간선은 5–6(6), 3–5(10), 5–7(14)이라 6을 먼저 붙인다. 그다음 후보는 3–5(10), 3–6(12), 5–7(14)이라 3이 붙는다. 싼 간선 3–4(4)는 3이 나무에 들어온 뒤에야 후보가 된다.
(다) 1바퀴: 1–2, 3–4, 5–6, 7–8. 2바퀴: 2–3, 3–5, 5–7.
세 방법 모두 같은 간선 일곱 개를 고르고 합은 \(2 + 3 + 4 + 6 + 7 + 10 + 14 = 46\)이다. 간선의 비용이 모두 달라서 최소 비용 신장 트리가 하나뿐이기 때문이다.
p5 · 버리기 전략
p4의 그래프는 간선이 10개이고 신장 트리에는 7개만 필요하다. 7개를 고르는 대신 3개를 버려도 된다. (가) “비싼 간선부터 보며, 그 간선을 빼도 그래프가 이어져 있으면 버린다”로 버리는 간선 셋을 쓰라. (나) “사이클을 하나 찾아 그 위에서 가장 비싼 간선을 버리기를, 사이클이 없을 때까지”로 하면 무엇이 남는가?
풀이 전략
사이클 위의 간선 하나를 빼도 그래프는 이어져 있다. 그래서 “빼도 이어져 있나”는 “이 간선이 사이클 위에 있나”와 같은 질문이다. 비싼 것부터 내려오며 그 간선을 지나는 사이클이 남아 있는지 본다.
풀이
(가) 비싼 순서: 5–7(14), 3–6(12), 3–5(10), 2–4(9), 1–3(8), 2–3(7), …
- 5–7(14): 빼면 7, 8이 떨어진다. 남긴다.
- 3–6(12): 3–5–6으로 돌아갈 수 있다. 버린다.
- 3–5(10): 3–6을 버린 뒤라 5, 6으로 가는 길이 이것뿐이다. 남긴다.
- 2–4(9): 2–3–4로 돌아갈 수 있다. 버린다.
- 1–3(8): 1–2–3으로 돌아갈 수 있다. 버린다.
- 2–3(7)부터는 모두 빼면 끊어진다. 남긴다.
버린 것은 3–6, 2–4, 1–3이고 남은 일곱 개의 합은 46이다.
(나) 작은 사이클은 1–2–3, 2–3–4, 3–5–6의 셋이다(1–2–4–3처럼 둘을 이어 붙인 큰 사이클도 있다). 어느 사이클부터 보든 그 위에서 가장 비싼 간선으로 1–3(8), 2–4(9), 3–6(12)이 버려지고 같은 일곱 개가 남는다. 합은 46이다. 고르는 전략 셋과 버리는 전략 둘이 모두 같은 나무를 준다.