손은 컴퓨터보다 빠르다

https://www.acmicpc.net/problem/13313

그래프 4-coloring 백트래킹 알고리즘에 대한 adversarial input을 생성하는 문제이다. 상대방의 백트래킹 코드가 50,000,000번 이상의 DFS 호출을 하도록 만드는 그래프와, 그 그래프의 올바른 4색 칠하기 결과를 함께 출력해야 한다.

상대 코드 분석

상대의 백트래킹은 이런 구조이다:

#include<stdio.h>
#include<vector>
#include<cassert>
#include<stdlib.h>
using namespace std;

const int MX = 55;
const int LIM = 50000000;

vector<int> G[MX];
int C[MX], cnt = 0;
int N, M;

bool dfs(int x)
{
 if( x == N+1 ) return true;
 cnt++;
 if( cnt >= LIM ) return true;
 int msk = 0;
 for(int c : G[x]){
  msk |= 1<<C[c];
 }
 for(int i = 1; i <= 4; i++){
  if( msk & 1<<i ) continue;
  C[x] = i;
  if( dfs(x+1) ) return true;
  C[x] = 0;
 }
 return false;
}

bool chk[MX][MX];
int main()
{
 assert(scanf("%d%d", &N, &M) == 2);
 assert(2 <= N && N <= 50 && 0 <= M && M <= N(N-1)/2);
 for(int i = 1; i <= M; i++){
  int a, b;
  assert(scanf("%d%d", &a, &b) == 2);
  assert( 1 <= a && a <= N && 1 <= b && b <= N && a != b && !chk[a][b]);
  chk[a][b] = chk[b][a] = 1;
  G[a].push_back(b);
  G[b].push_back(a);
 }
 dfs(1);
 assert(cnt >= LIM);

 for(int i = 1; i <= N; i++){
  C[i] = 0;
  assert(scanf("%d", C+i) == 1);
  assert(1 <= C[i] && C[i] <= 4);
 }
 for(int i = 1; i <= N; i++){
  for(int c : G[i]){
   assert(C[i] != C[c]);
  }
 }
 return 0;
}

• 정점 1부터 N까지 순서대로 색칠한다
• 각 정점에서 색 1, 2, 3, 4를 순서대로 시도한다
• 이미 칠해진 이웃의 색과 겹치면 건너뛴다
• cnt가 50,000,000(=LIM) 이상이 되면 강제 종료한다
• 종료 후 cnt >= LIM을 assert로 검증한다

핵심은 백트래커가 색을 작은 번호부터 시도하고, 정점 번호 순서로 칠한다는 점이다. 이를 이용해 “처음 시도하는 배정이 실패하고, 실패가 늦게 발견되는” 그래프를 만들면 된다.

아이디어

지연된 제약 조건(delayed constraint)을 핵심 아이디어로 사용한다.

백트래커는 현재 정점의 이웃 중 이미 칠해진 정점만 확인한다. 따라서 번호가 큰 정점들 사이의 제약은 나중에야 발견된다. “자유로운 선택”을 앞에, “제약 검증”을 뒤에 배치하면, 백트래커가 모든 자유 선택을 소진한 뒤에야 실패를 감지하게 만들 수 있다.

1. 정점 1, 2, 3, 4를 완전 그래프 K4로 연결한다. 백트래커는 각각 색 1, 2, 3, 4를 배정한다 (유일한 선택).
2. 정점 5, 6을 각각 정점 3, 4에만 연결한다. 색 3, 4가 차단되므로 색 {1, 2} 중 선택해야 한다. 백트래커는 색 1을 먼저 시도한다.
3. 정점 7부터 31까지도 각각 정점 3, 4에만 연결한다. 마찬가지로 색 {1, 2} 중 독립적으로 선택한다. 이 정점들은 서로 연결되지 않으므로 2^25가지 조합이 존재하고, 백트래커는 뒤쪽 전파 정점에서 실패를 발견하기 전에 이 조합을 전부 시도하게 된다.
4. 정점 32: 정점 5, 3, 4에 연결 → 정점 5의 “반대색”으로 강제된다
5. 정점 33: 정점 6, 3, 4, 32에 연결 → 정점 6의 “반대색”으로 강제된다
6. 간선 32-33: 두 전파 정점이 다른 색이어야 함 → 정점 5 ≠ 정점 6 강제

백트래커의 동작

1. 정점 1-4: K4이므로 색 1, 2, 3, 4 배정 (백트래킹 없음)
2. 정점 5: 색 1 시도 (성공)
3. 정점 6: 색 1 시도 (성공) — 아직 5와의 제약은 보이지 않음
4. 정점 7-31: 각각 색 1 시도 (성공)
5. 정점 32: 5(=1), 3(=3), 4(=4) 차단 → 색 2 강제
6. 정점 33: 6(=1), 3(=3), 4(=4), 32(=2) 차단 → 색 없음 실패. 실패 후 정점 31로 백트래킹하여 색 2를 시도하지만, 정점 33의 실패는 오직 (5=1, 6=1)이라는 배정 때문이므로, 정점 7-31의 어떤 조합이든 똑같이 실패한다.

DFS 호출 수 계산

정점 v에서의 DFS 호출 수를 f(v)라 하면:

• f(33) = 1 (호출 즉시 실패)
• f(32) = 1 + f(33) = 2 (색 2만 유효, 33 호출 후 실패)
• f(v) = 1 + 2·f(v+1) (v = 7..31, 색 2가지 각각에서 재귀)

이 점화식을 풀면:

f(v) = 3·2^(32-v) - 1
f(7) = 3·2^25 - 1 ≈ 100,663,295

정점 1-6의 호출 6회를 더하면 총 약 1억 회로, LIM(5천만)을 충분히 초과한다.

정답 색칠 구성

(5=1, 6=1)이 실패하는 이유는 5 ≠ 6이 강제되기 때문이므로, 5=1, 6=2 (또는 5=2, 6=1)로 배정하면 된다:

정점:  1  2  3  4  5  6  7...31  32  33
색:    1  2  3  4  1  2  1...1   2   1

• 32는 5(=1)의 반대 → 2
• 33은 6(=2)의 반대 → 1
• 32(=2) ≠ 33(=1) ✓

최종 코드

#include <iostream>
using namespace std;

int main() {
    int n=33;
    int m=6+272+3+4;

    cout<<n<<" "<<m<<"\n";
    cout<<"1 2\n1 3\n1 4\n2 3\n2 4\n3 4\n";
    for (int i=5;i<=31;i++) cout<<i<<" 3\n"<<i<<" 4\n";

    cout<<"32 5\n32 3\n32 4\n";
    cout<<"33 6\n33 3\n33 4\n32 33\n";
    cout<<"1 2 3 4 1 2";

    for (int i=7;i<=31;i++) cout<<" 1";
    cout<<" 2 1\n";

    return 0;
}