BOJ 13313 - 손은 컴퓨터보다 빠르다 링크
(2024.05.09 기준 G1)

문제

주어지는 백트래킹 코드가 시간초과 나면서, 두 정점의 색이 항상 다르도록 $4$가지 색으로 칠해진 그래프 하나를 출력

알고리즘

해 구성하는 문제

풀이

주어진 백트래킹 코드를 읽어보면, 인덱스가 증가하는 순서로 정점을 하나씩 칠해보는 방식이다.
그러면 최대한 앞에서 잘못 칠하게끔 유도하면서, 최대한 뒤에서 알아차릴 수 있게끔 해야 한다.

다양한 풀이가 존재하지만 나는 다음과 같은 그래프를 사용했다.

처음엔 $1$, $6$, $11$, $16$번 정점은 각각 $1$, $2$, $3$, $4$번 색을 칠해지게 된다.
그러면 $50$번에 도착했을 때 잘못 칠했음을 알 수 있게 된다.

$17$~$49$번 정점에서 가능한 경우의 수를 전부 시도해볼 것이므로 결국 시간초과가 나게 된다.

코드

• Text

50 60
1 2
1 3
1 4
2 3
2 4
3 4
5 6
5 7
5 8
6 7
6 8
7 8
9 10
9 11
9 12
10 11
10 12
11 12
13 14
13 15
13 16
14 15
14 16
15 16
1 50
6 50
11 50
16 50
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
1 2 3 4 4 1 2 3 3 4 1 2 2 3 4 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 2