조합 색칠문제는 순서 관계없이 선택의 조합을 계산하는 경우의 수 유형입니다. 백트래킹으로 모든 경우를 탐색한 뒤 메모이제이션으로 중복 계산을 제거하면 효율적으로 풀 수 있어요.
조합 색칠문제의 기본 원리
조합 색칠문제는 그래프 색칠에서 경우의 수를 구하는 응용 유형입니다. 가장 중요한 포인트는 선택의 순서는 무관하고 조합만 다르면 다른 경우라는 점이에요.
예를 들어 7개의 꼭짓점 중 특정 색칠 규칙에 따라 몇 가지 색칠 방법이 가능한가를 묻는 식입니다. 핵심은 edge 연결 상태에 따라 색칠 가능한 꼭짓점의 개수가 동적으로 변한다는 거예요.
따라서 정적인 공식(nCr = n!/(r!(n-r)!))만으로는 풀 수 없고, 각 선택 단계마다 다음 상황을 재계산해야 합니다.
조합 색칠의 3가지 핵심 요소:
– 조합: 순서 무관 (nCr)
– 색칠 제약: edge로 연결된 꼭짓점은 같은 색 불가
– 경우의 수: 순서를 고정한 후 색상 할당 조합 계산
실제 예시: 정삼각형의 3개 꼭짓점을 빨강/파랑/노랑 3가지 색으로 칠하는데 인접한 꼭짓점이 같은 색이면 안 된다면, 3×2×1 = 6가지가 아니라 실제로는 각 단계마다 선택지가 줄어들어 더 적은 경우만 가능해요.
백트래킹으로 모든 경우의 수 탐색
조합 색칠문제를 푸는 첫 번째 방법은 백트래킹입니다. 이는 깊이 우선 탐색(DFS)으로 모든 가능한 색칠 방법을 시도하고, 조건을 위반하면 즉시 돌아가는 기법이에요.
백트래킹의 5단계 절차:
- 현재 꼭짓점 선택 — 아직 색칠하지 않은 첫 꼭짓점 선택
- 사용 가능한 색 탐색 — 인접한 꼭짓점과 색이 겹치지 않는 색만 시도
- 색 할당 — 조건을 만족하는 색 지정
- 다음 단계 진행 — 재귀 호출로 다음 꼭짓점 진행
- 실패 시 복원 — 조건 위반 시 색 제거하고 다른 색 시도
이 방식은 모든 경우를 탐색하기 때문에 정확한 답을 보장하지만, 탐색 대상이 많으면 시간이 매우 오래 걸리는 단점이 있어요.
백트래킹의 장단점:
– 장점: 모든 경우를 빠짐없이 탐색하므로 100% 정확
– 단점: 꼭짓점 15개 이상이면 시간 초과 가능성 높음
백트래킹은 조합론 문제의 가장 기초적이면서도 강력한 방법입니다. 이를 통해 문제의 모든 가능성을 파악한 후에 최적화 방법을 생각하는 게 좋은 학습 순서예요.
메모이제이션으로 성능 최적화
백트래킹만으로는 시간 초과가 나는 경우가 많습니다. 이때 사용하는 게 메모이제이션입니다. 같은 상황이 반복되면 이전 계산 결과를 재사용하는 방식이에요.
메모이제이션의 핵심 원리:
- 상태 저장: (현재 꼭짓점, 현재까지의 색칠 상태) → 가능한 경우의 수
- 중복 제거: 같은 상태를 다시 만나면 저장된 값으로 즉시 반환
- 계산량 대폭 감소: 반복 탐색 제거로 수십 배 이상 빨라짐
메모이제이션 성능 비교:
| 방법 | 시간복잡도 | 공간복잡도 | 추천 용도 |
|---|---|---|---|
| 백트래킹만 | O(c^n) | O(n) | 꼭짓점 5-8개 |
| 메모이제이션 | O(2^n) | O(2^n) | 꼭짓점 10-20개 |
메모이제이션을 적용하면 메모리를 더 쓰지만 실행 시간이 획기적으로 단축돼요. 꼭짓점이 15개 이상이면 거의 필수입니다.
메모이제이션 적용 예시: 꼭짓점 10개, 색 4가지인 경우 백트래킹은 4^10 = 백만 번 이상 탐색하지만, 메모이제이션으로 같은 상태 반복을 제거하면 수천 번으로 줄어들 수 있어요.
조합 색칠문제 풀이 전략
조합 색칠문제를 효율적으로 풀려면 단계별로 접근해야 해요.
1단계: 문제 분석
– 그래프 구조 파악 (꼭짓점 개수, edge 연결 관계)
– 색칠 규칙 명확화 (인접 금지, 거리 제약 등)
– 구해야 할 값 정의 (경우의 수 vs 최소 색 개수)
2단계: 간단한 예로 검증
– 작은 입력으로 손으로 계산하여 정답 확인
– 예: 3개 꼭짓점, 3개 색 → 몇 가지 경우?
3단계: 백트래킹 구현
– 모든 경우를 탐색하는 기본 코드 작성
– 작은 입력(5-8개 꼭짓점)에서 정확성 검증
4단계: 시간 초과 판정
– 중간 크기 입력(10-15개 꼭짓점)에서 실행 시간 측정
– 1-2초 이상 걸리면 최적화 필수
5단계: 메모이제이션 추가
– 상태를 명확히 정의하고 dp 딕셔너리 추가
– 캐시 히트율 확인으로 성능 개선 검증
이 순서로 진행하면 복잡한 조합 문제도 체계적으로 해결할 수 있어요. 특히 코딩 테스트나 알고리즘 학습에서 정확성과 효율성의 균형을 이루는 데 도움이 됩니다.
자주 묻는 질문
모든 가능한 색칠 방법을 하나씩 시도해서 조건을 만족하는 경우만 센다는 뜻이에요. 예: 7개 꼭짓점 그래프라면, 첫 번째 꼭짓점부터 마지막까지 색을 할당하면서 "인접한 꼭짓점이 같은 색이면 즉시 멈추고 다른 색 시도"하는 방식으로 탐색합니다. 이렇게 성공한 색칠만 세면 정확한 경우의 수를 얻어요.
같은 상태(색칠 진행 상황)를 만날 때마다 바로 저장된 답을 꺼내 쓰기 때문에, 재귀 호출이 크게 줄어들어요. 예를 들어 꼭짓점 10개, 색 3가지인 문제에서 백트래킹 연산량은 3×2×2×2×… (약 3천 번 호출)인데, 메모이제이션을 쓰면 중복 상태를 스킵해서 수백 번으로 줄어들 수 있습니다.
네, 큰 영향을 줍니다. degree가 높은 꼭짓점(많은 이웃을 가진)은 제약이 많아서 색 선택지가 적어요. 이런 꼭짓점을 먼저 처리하면 그 이웃들의 색이 일찍 고정되고, 전체 탐색 트리의 깊이와 너비가 훨씬 줄어들어요. 실제로 무작위 순서와 degree 순서로 같은 문제를 풀면 수배에서 수십 배 차이가 날 수 있습니다.
보통 꼭짓점이 50개 미만이라면 문제 없어요. 하지만 대부분의 프로그래밍 언어는 기본 재귀 깊이 제한이 1000-10000 정도이므로, 매우 큰 그래프(100개 이상 꼭짓점)를 다룰 때는 반복문으로 스택을 직접 관리하거나 메모이제이션으로 탐색 깊이 자체를 줄여야 해요.
네, 완전히 적용돼요. 부분 집합 찾기, N-Queen 문제, 순열/조합 생성, Sudoku 풀이, 부분 합 등 거의 모든 제약 조건 만족(CSP) 문제에 같은 백트래킹 + 메모이제이션 패턴을 쓸 수 있어요. 이 글에서 배운 탐색 전략과 최적화 기법이 다른 문제로도 바로 응용됩니다.