[SWEA 5286][Python][파이썬 S/W 문제해결 최적화] 5일차 - 그래프 색칠하기

코드

## SWEA 5286 -- dfs 풀이
def dfs(node,color):
    global result
    visited[node] = 1
    color_arry[node] = color
    color_list = [i for i in range(1, M + 1)]
    for next in node_arry[node]:
        if visited[next] == 0:
            tmp_color_list = list(set([color_arry[i] for i in node_arry[next]]))
            available_color_list = [c for c in color_list if c not in tmp_color_list]
            if not available_color_list:
                result = 0
                return
            for next_color in available_color_list :
                dfs(next, next_color)

T = int(input())
for test_case in range(1, T + 1):
    N,E,M = map(int, input().split())
    arry = [ list( map(int, input().split()) )  for _ in range(E) ]
    node_arry = [[] for _ in range(N+1) ]
    for s,e in arry :
        node_arry[s].append(e)
        node_arry[e].append(s)
    color_arry = [0]*(N+1)
    visited = [0]*(N+1)
    result = 1
    dfs(1,1)
    print(f"#{test_case} {result}")

 

풀이

연결된 node를 dfs로 탐색하며 color_list에서 인접한 node의 color를 빼주고 다음 노드로 진행했다. 

만약 color_list에서 인접한 node의 color를 뺐을 때 남은 color가 없으면 칠할 수 없는 그래프이다.