백준 13265 색칠하기 / python

문제 : 13265

풀이 point

그래프 색칠하기 문제는 m-coloring 문제로 굉장히 유명하다. 이 문제는 coloring 문제의 축소 버전으로 연결 그래프에서 2가지 색상으로만 색칠이 가능한가를 묻고 있다.

그래프 탐색을 통해 인접한 노드가 같은 색깔로 칠해져야만 하는 경우는 실패이다.
방문 배열과 컬러 배열로 노드를 방문했는지, 방문했다면 어떤 색인지 확인하는 방식으로 문제를 풀 수 있다.

풀이 방법

먼저 입력받은 그래프를 만들어준다.(양방향 그래프이다) 그 다음 bfs를 통해 노드를 하나씩 탐색해준다. 맨 처음 입력받은 노드에 방문표시와 색깔 표시를 해준다. 그 후 그 노드와 연결된 노드들을 하나씩 넣고 꺼내가면서 모든 노드가 인접한 노드와 다른 색상으로 칠해지면 possible을 출력하고, 그렇지 않다면 impossible을 출력한다.

이때 주의 할 점은 모든 노드가 연결되어 있다는 가정이 없으므로 그래프가 끊길 수 있다. 즉 그래프가 2개 만들어질수도 있다는 뜻. 그러므로 마지막에 color배열을 조사하면서 색칠이 되지 않은 노드가 있다면 그 부분부터 다시 탐색 해야한다.

코드

#백준, 13265 색칠하기

import sys
from collections import deque
input = sys.stdin.readline

def bfs(v):
    Q.append(v)
    visited[v] = 1
    color[v] = 1

    while Q:
        node = Q.popleft()
        
        for i in range(len(graph[node])):
            next = graph[node][i]
            if visited[next] == 0:
                visited[next] = 1
                color[next] = 2 if color[node] == 1 else 1
                Q.append(next)
            
            if visited[next] == 1 and color[node] == color[next]:
                return False
    return True

T = int(input())

for _ in range(T):
    N, M = map(int, input().rstrip().split())
    graph = [[] for _ in range(N+1)]
    color = [0 for _ in range(N+1)]
    visited = [0 for _ in range(N+1)]
    
    Q = deque()

    for i in range(M):
        a, b = map(int, input().rstrip().split())
        graph[a].append(b)
        graph[b].append(a)
    
    flag = False

    if not bfs(1):
        flag = True
    
    if not flag:
        for i in range(len(color)):
            if color[i] == 0:
                if not bfs(i):
                    flag = True
                    break
    
    print("possible") if flag == False else print("impossible")

느낀점

개인적으로 여러 테스트 케이스를 한꺼번에 받아 출력하는 문제라 조기 종료하는 방식을 구상하는 것이 어려웠다. 그 외에도 이런 문제들을 굉장히 유명한 문제여서 한번에 다른 문제들도 풀어보는 것이 좋다고 생각한다. 여담이지만 파이썬의 삼항연산자는 참... 직관적이지 못한거 같다.