[SWEA] 5286 그래프 색칠하기

링크: 5286. 파이썬 S/W 문제해결 최적화 5일차 - 그래프 색칠하기

코드

def coloring():
    # 전체 색 - 인접한 노드들 색
    colors = set([i for i in range(1, m + 1)])  # 사용 가능한 색상

    for adjV in adjacent:
        colors -= colored[adjV]

    if not colors:
        return False

    colored[v] = {min(colors)}

    return True


for t in range(1, int(input())+1):
    n, e, m = map(int, input().split())
    graph = dict()
    answer = 1

    colored = [{0} for _ in range(n+1)]  # 뭐로 칠했는지 저장

    for _ in range(e):
        v1, v2 = map(int, input().split())
        graph[v1] = graph.get(v1, set()).union({v2})
        graph[v2] = graph.get(v2, set()).union({v1})

    for v in graph:
        adjacent = graph[v]  # 인접 점들을 확인

        if not coloring():
            answer = 0
            break

    print(f'#{t} {answer}')