그래프 색칠 문제

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D', 'F'],
    'C': ['A', 'B', 'E', 'F'],
    'D': ['B'],
    'E': ['C', 'F'],
    'F': ['B', 'C', 'E'],
}

def greedy(graph, order):
    color = {}
    for v in order:
        used = {color[u] for u in graph[v] if u in color}   # 이웃이 쓰는 색
        c = 1
        while c in used:
            c += 1
        color[v] = c                                          # 남은 가장 작은 번호
    return color

c1 = greedy(graph, 'ABCDEF')
print(c1, max(c1.values()))
# {'A': 1, 'B': 2, 'C': 3, 'D': 1, 'E': 1, 'F': 4} 4

order = sorted(graph, key=lambda v: -len(graph[v]))   # 이웃이 많은 정점부터
c2 = greedy(graph, order)
print(order, c2, max(c2.values()))
# ['B', 'C', 'F', 'A', 'E', 'D'] {'B': 1, 'C': 2, 'F': 3, 'A': 3, 'E': 1, 'D': 2} 3

def can_color(graph, m, order):
    color = {}
    tries = 0

    def solve(i):
        nonlocal tries
        if i == len(order):
            return True
        v = order[i]
        for c in range(1, m + 1):
            tries += 1
            if all(color.get(u) != c for u in graph[v]):   # 이웃과 충돌하지 않으면
                color[v] = c
                if solve(i + 1):
                    return True
                del color[v]                              # 막히면 되돌아간다
        return False

    ok = solve(0)
    return ok, color, tries

print(can_color(graph, 2, 'ABCDEF'))   # (False, {}, 10)
print(can_color(graph, 3, 'ABCDEF'))   # (True, {'A': 1, 'B': 2, 'C': 3, 'D': 1, 'E': 2, 'F': 1}, 13)

conflicts = {                                         # 같은 학생이 함께 듣는 과목
    '수학': ['물리', '화학'],
    '물리': ['수학', '화학', '영어'],
    '화학': ['수학', '물리'],
    '영어': ['물리', '국어'],
    '국어': ['영어'],
}
slots = greedy(conflicts, sorted(conflicts, key=lambda v: -len(conflicts[v])))
by = {}
for k, s in slots.items():
    by.setdefault(s, []).append(k)
print(by)                  # {1: ['물리', '국어'], 2: ['수학', '영어'], 3: ['화학']}

from collections import deque

def two_colorable(graph):
    color = {}
    for s in graph:
        if s in color:
            continue
        color[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for u in graph[v]:
                if u not in color:
                    color[u] = 1 - color[v]       # 이웃은 반대 색
                    q.append(u)
                elif color[u] == color[v]:
                    return False
    return True

square = {'a': ['b', 'd'], 'b': ['a', 'c'], 'c': ['b', 'd'], 'd': ['c', 'a']}
tri = {'a': ['b', 'c'], 'b': ['a', 'c'], 'c': ['a', 'b']}
print(two_colorable(square), two_colorable(tri), two_colorable(graph))   # True False False