문제 보기 · Level 5 · 2017 카카오코드 본선 · 정답률 1% · 푼 사람 86명 (2026-09-30 기준)1
문제
그래프 G의 정점은 1 ~ n, 간선은 1 ~ m번이다. 간선 i는 a[i − 1]과 b[i − 1]을 잇고, 같은 두 정점 사이 간선은 하나뿐이며 자기 자신을 잇는 간선은 없다. 끝점을 공유하지 않는 간선들의 집합을 매칭(matching)이라 한다.
크기가 k 이상인 두 매칭 M_0과 M_t가 주어진다. 한 단계에 간선 하나를 넣거나 빼서 M_0을 M_t로 바꾼다. 단계마다 결과가 매칭이어야 하고, 중간 매칭의 크기는 k − 2 이상이어야 한다. 바꾸는 과정을 [0(빼기) 또는 1(넣기), 간선 번호] 목록으로 돌려준다. 답이 여럿이면 아무거나 된다.
- n ≤ 100,000, m ≤ 1,000,000, 1 ≤ k ≤ 50,000
- e1, e2: M_0, M_t의 간선 번호 목록 (크기 m1, m2 ≥ k)
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
그래프 표현: 정점마다 “M_0에만 있는 간선”과 “M_t에만 있는 간선”을 하나씩 적어 둔다. 두 종류를 번갈아 밟으며 한 줄로 따라가면(깊이 우선 탐색처럼 끝까지) 덩어리가 경로나 사이클로 나온다.
1단계 · 작은 예로 손으로 풀기
문제의 예시다. 간선은 1(1–2), 2(1–3), 3(2–3), 4(2–4), 5(3–5), 6(4–5)이고, M_0 = {3, 6}, M_t = {2, 4}, k = 2다.
바꿀 간선만 보면 1 –2– 3 –3– 2 –4– 4 –6– 5로 한 줄이다(가운데 숫자가 간선 번호). 넣을 간선(2, 4)과 뺄 간선(3, 6)이 번갈아 나온다.
- 간선 2는 정점 3에서 간선 3과 부딪힌다. 3을 빼면(크기 1) 2를 넣을 수 있다(크기 2).
- 간선 4는 정점 4에서 간선 6과 부딪힌다. 6을 빼고(크기 1) 4를 넣는다(크기 2).
답은 [[0, 3], [1, 2], [0, 6], [1, 4]]이고, 크기는 1까지만 내려간다. 넣을 간선이 있는 끝에서 시작하면 한 번 빼고 바로 넣을 수 있다.
2단계 · 가장 단순한 방법과 그 속도
M_0에만 있는 간선을 다 빼고 M_t에만 있는 간선을 다 넣으면 단계는 가장 적다. 하지만 중간 크기가 두 매칭에 함께 있는 간선 수까지 떨어진다. 6단계의 그래프에서는 1까지 떨어져 k − 2 = 5를 못 지킨다. 그렇다고 가능한 모든 순서를 찾아보면 매칭의 수가 너무 많다.
3단계 · 핵심 아이디어
- 바꿀 간선만 본다: 두 매칭에 다 있는 간선은 그대로 둔다. M_0에만 있는 간선(뺄 것)과 M_t에만 있는 간선(넣을 것)만 남긴다(대칭 차집합). 기호로는 \(M_0 \oplus M_t = (M_0 - M_t) \cup (M_t - M_0)\)이다(집합의 ⊕).
- 덩어리는 경로나 사이클: 한 정점에는 뺄 간선이 많아야 하나, 넣을 간선이 많아야 하나 붙는다. 둘 다 매칭이기 때문이다. 그래서 남은 간선을 따라가면 뺄 것과 넣을 것이 번갈아 나오는 경로나 사이클이 된다. 사이클은 길이가 짝수라 두 종류의 수가 같다.
- 경로의 끝은 비어 있다: 경로 끝의 넣을 간선은 바깥 끝점에 M_0 간선이 없다. 있었다면 그 간선도 같은 덩어리에 들어갔거나, M_t에도 있는 간선이라 넣을 간선과 부딪혔을 것이다.
- 한 덩어리 처리: 넣을 간선은 양옆의 뺄 간선이 다 빠져야 넣을 수 있다. 그래서 덩어리를 한쪽 끝부터 훑으며 뺄 간선을 빼고, 막힘이 풀린 넣을 간선을 바로 넣는다. 경로는 넣을 간선이 있는 끝에서 시작한다. 크기는 이렇게 움직인다.
| 덩어리 | 가장 많이 내려갈 때 | 끝날 때 |
|---|---|---|
| 넣을 것이 하나 많은 경로 | −1 | +1 |
| 수가 같은 경로 | −1 | 0 |
| 사이클 (처음에 둘을 빼야 하나를 넣는다) | −2 | 0 |
| 뺄 것이 하나 많은 경로 | −2 | −1 |
- 덩어리 순서: 커지는 덩어리 → 그대로인 덩어리 → 작아지는 덩어리 순서로 한다. 앞의 두 종류를 하는 동안 크기는 |M_0| ≥ k 이상에서 출발해 2까지만 내려가니 k − 2 이상이다. 작아지는 덩어리는 r개 남았을 때 크기가 |M_t| + r ≥ k + 1이다. 거기서 2 내려가도 k − 1 이상이다.
4단계 · 코드 흐름
- only0 = M_0에만 있는 간선, only1 = M_t에만 있는 간선. 정점마다 붙은 only0 간선(at0), only1 간선(at1)을 적는다.
- 한 종류만 붙은 정점은 경로의 끝이다. 거기서 두 종류를 번갈아 따라가며 경로를 딴다. 남은 간선은 사이클이라, 아무 간선에서 출발해 한 바퀴 돈다.
- 덩어리마다 두 종류의 수를 세어 커지는 것, 그대로인 것, 작아지는 것으로 나눈다. 경로가 뺄 간선으로 시작하고 넣을 간선으로 끝나면 뒤집는다.
- 순서대로 덩어리를 처리한다. 넣을 간선마다 “아직 남은 이웃 뺄 간선 수”를 세어 두고, 뺄 간선을 뺄 때마다 이웃의 수를 줄여 0이 되면 넣는다.
5단계 · 파이썬 코드
def solution(n, m, a, b, k, m1, m2, e1, e2):
only0 = set(e1) - set(e2) # 뺄 간선
only1 = set(e2) - set(e1) # 넣을 간선
at0, at1 = {}, {} # 정점 → 붙은 뺄 간선, 넣을 간선
for e in only0:
at0[a[e - 1]] = at0[b[e - 1]] = e
for e in only1:
at1[a[e - 1]] = at1[b[e - 1]] = e
def other(e, v):
return b[e - 1] if a[e - 1] == v else a[e - 1]
seen = set()
def walk(v, e): # 두 종류를 번갈아 밟으며 간다
seq = []
while e is not None and e not in seen:
seen.add(e)
seq.append(e)
v = other(e, v)
e = (at1 if e in only0 else at0).get(v)
return seq
comps = [] # (경로인가, 간선 순서)
for v in set(at0) | set(at1):
if (v in at0) != (v in at1): # 한 종류만 붙은 정점 = 경로의 끝
e = at0.get(v) or at1.get(v)
if e not in seen:
comps.append((True, walk(v, e)))
for e in list(only0) + list(only1): # 남은 것은 사이클
if e not in seen:
comps.append((False, walk(a[e - 1], e)))
grow, even, shrink = [], [], []
for is_path, seq in comps:
c0 = sum(e in only0 for e in seq)
c1 = len(seq) - c0
if is_path and seq[0] in only0 and seq[-1] in only1:
seq.reverse() # 넣을 간선이 있는 끝에서 시작한다
(grow if c1 > c0 else even if c1 == c0 else shrink).append((is_path, seq))
steps = []
for is_path, seq in grow + even + shrink:
size = len(seq)
def nbrs(i): # 덩어리 안에서 i번째 간선의 이웃
out = []
if i > 0 or not is_path:
out.append(seq[i - 1])
if i < size - 1:
out.append(seq[i + 1])
elif not is_path:
out.append(seq[0])
return out
block = {} # 넣을 간선 → 남은 이웃 뺄 간선 수
for i, e in enumerate(seq):
if e in only1:
block[e] = sum(f in only0 for f in nbrs(i))
if block[e] == 0:
steps.append([1, e])
for i, e in enumerate(seq):
if e in only0:
steps.append([0, e])
for f in nbrs(i):
if f in only1:
block[f] -= 1
if block[f] == 0:
steps.append([1, f])
return steps
walk는 재귀 대신 while로 따라간다. 경로가 수만 간선으로 길어도 재귀 한도에 걸리지 않는다.seq[i - 1]은 i = 0일 때 마지막 간선이다. 사이클에서는 처음과 끝이 이웃이라 그대로 쓴다. 경로에서는 쓰지 않는다.- k는 코드에서 쓰지 않는다. 덩어리 순서가 k − 2 조건을 늘 지켜 준다.
6단계 · 실행 추적
정점 17개, 간선 13개짜리 그래프다. 간선 13(16–17)은 두 매칭에 다 있어 그대로 둔다. k = 7이고 처음 크기는 7이다.
| 덩어리 | 간선 (끝점, 종류) | 단계 | 크기 |
|---|---|---|---|
| 커지는 경로 | 1(1–2, 넣기), 2(2–3, 빼기), 3(3–4, 넣기) | 2 빼기, 1 넣기, 3 넣기 | 7 → 6 → 7 → 8 |
| 수가 같은 경로 | 4(5–6, 빼기), 5(6–7, 넣기) | 4 빼기, 5 넣기 | 8 → 7 → 8 |
| 사이클 | 6(8–9, 빼기), 7(9–10, 넣기), 8(10–11, 빼기), 9(11–8, 넣기) | 6, 8 빼기, 7, 9 넣기 | 8 → 7 → 6 → 7 → 8 |
| 작아지는 경로 | 10(12–13, 빼기), 11(13–14, 넣기), 12(14–15, 빼기) | 10, 12 빼기, 11 넣기 | 8 → 7 → 6 → 7 |
사이클에서 간선 7은 6과 8 사이에 있어, 둘 다 빠진 뒤에야 들어간다. 크기는 6까지만 내려가 k − 2 = 5를 지킨다. 끝 크기 7은 |M_t|와 같다.
7단계 · 복잡도와 흔한 실수
바꿀 간선마다 몇 번씩만 보니 \(O(m_1 + m_2)\)다. 정점 10만, 간선 100만, 매칭이 각각 4만 7천여 개인 입력에서 0.2초쯤 걸렸다.
- 덩어리를 찾은 순서대로 처리한다. 작아지는 덩어리 둘이 먼저 오면 크기가 3 내려간다. 6단계와 비슷한 그래프(작아지는 경로 둘, 커지는 경로 둘, k = 6)에서 작아지는 것부터 하면 크기가 3까지 떨어져 k − 2 = 4를 못 지킨다.
- 두 매칭에 다 있는 간선까지 뺐다 넣는다. 단계만 늘고 크기가 더 내려간다.
- “실행”의 예시 답과 다르다고 틀린 줄 안다. 문제 알림대로 답이 여럿일 수 있고, “코드 채점”에서는 맞는 답을 모두 받는다.