백준 24782 - Coloring Graphs (Python)

문제 정보

• https://www.acmicpc.net/problem/24782
• 백트래킹, 브루트포스

---

문제 정리

그래프가 주어지고 아래 규칙에 따라 정점을 색칠해야 한다.

• 두 정점이 이어진 간선이 존재할 때, 이 정점들은 같은 색으로 칠할 수 없다.

이를 만족하면서 그래프의 정점을 전부 칠할 때, 필요한 색의 최소 개수를 구하는 문제이다.

---

풀이

• $N \leq 11$이다.
  왠지 백트래킹을 써야 할 것 같다.

• 그냥 단순하게 N개의 정점에 색을 하나씩 할당하면서 모든 경우를 보면 $N^{N}$이고, $N = 11$일 경우 약 2800억의 상태공간이 생겨 TLE가 발생하게 된다.

• 관찰1 : 사실 정점이 11개라도 모든 정점에 전부 다 다른 색을 할당해야 하는 경우는 완전 그래프일 때 말고는 없다.
  따라서, 색을 많이 사용해야 하는 그래프가 그렇게 많지 않다는 것이다.

• 관찰2 : 관찰1의 확장으로, 그래프가 주어질 때 i개의 색을 사용해서 그래프를 전부 다 칠할 수 있는지 i를 1씩 증가시켜가며 체크해보자.

• 관찰3 : 또한, 현재 칠하는 정점이 i번째일 경우, i개 이하의 색만 사용해도 충분하다는 사실을 생각하자.
  즉, (1, 4, 2, 3)과 같은 경우는 탐색할 필요가 없다는 소리다.

---

후기

468ms는 관찰2까지만 적용시킨 풀이이고, 88ms는 관찰3까지 적용시킨 풀이이다.
시간이 확 줄어든 것을 확인할 수 있다.

---

코드

# 백준 24782

import io

input = io.BufferedReader(io.FileIO(0), 1<<18).readline


def DFS(N, K, graph, curV, colorList):
    if curV == N:
        return 1

    result = 0
    for curColor in range(min(K, curV+1)):
        # curV를 curColor로 칠할 수 있는지 체크
        canPaint = True
        for nextV in graph[curV]:
            if colorList[nextV] == curColor:
                canPaint = False
                break

        # 이후 재귀
        if canPaint == True:
            colorList[curV] = curColor
            result = max(result, DFS(N, K, graph, curV+1, colorList))
            colorList[curV] = -1

    return result


def solve(N, graph):
    # 첫 번째 색은 0번으로 미리 지정
    colorList = [-1] * N
    colorList[0] = 0

    # 그래프를 i색으로 칠할 수 있는지 체크
    for i in range(1, N):
        canPaint = DFS(N, i, graph, 1, colorList)
        if canPaint == 1:
            return i
    return N


def main():
    N = int(input())
    graph = []
    for _ in range(N):
        graph.append(list(map(int, input().split())))

    print(solve(N, graph))


main()