백준 13265. 색칠하기 (with Python)

문제

어린 토니킴은 색칠공부를 좋아한다.

토니킴은 먼저 여러 동그라미와 동그라미 두 개를 연결하는 직선들 만으로 그림을 그리고 (모든 동그라미들 사이에 직선이 있을 필요는 없다), 연결된 두 동그라미는 서로 색이 다르게 되도록 색을 칠하고자 한다.

이 그림을 색칠하는데 필요한 최소의 색의 개수를 구하는 문제는 어렵기 때문에 토니킴은 2 가지 색상으로 색칠이 가능한지의 여부만을 알고 싶어한다.

동그라미들의 번호와 동그라미들이 서로 연결된 직선에 대한 정보가 주어졌을 때, 이 동그라미들이 2 가지 색상으로 색칠이 가능한지 알아내자.

접근 방법

사실 dfs 분류로 보고 들어왔는데 문제 푸는건 bfs로 해결했다.
1. 동그라미를 하나씩 bfs로 이웃하는 동그라미를 방문하여 서로 다른 색으로 칠해주었다.
2. 그렇게 진행하다가 이웃한 동그라미의 색이 이미 칠해져있고 심지어 색이 같다면, impossible!!, 아니라면 끝까지 색을 다 칠하고 possible!!
3. 그리고 bfs탐색을 1회만 돌리는게 아니라 1번 동그라미를 기준으로 한번 돌리고 색이 안칠한 동그라미가 있을 수도 있으니 반복문으로 한번 더 돌렸다.
무슨 말이냐면,,

공이 모두 다 연결되어있는 경우도 있겠지만, 위와 같이 떨어져 있는 경우도 있을 수 있다. 그러면 1번 기준으로 bfs 돌려서 2,3번을 색칠하고 4번을 기준으로 또 bfs를 돌려야한다.

코드

from collections import deque

def bfs(x):
    global res
	
    # x는 1이 들어옴
    qu.append(x)
    # 1번 동그라미의 색은 1
    circles[x] = 1
    # 색깔 변수(기본값으로 그냥 2 해줬음)
    color = 2
    while qu:
    	# 큐에서 pop해서
        circle_num = qu.popleft()
        # 그 번호의 동그라미 색과 다른 색을 color 변수에 저장(1이라면 2를, 2라면 1을)
        if circles[circle_num] == 1:
            color = 2
        else:
            color = 1
        # 해당 동그라미 이웃 방문
        for i in info[circle_num]:
        	# 만약 방문을 안한 원이면
            if circles[i] == 0:
            	# 색을 칠하고
                circles[i] = color
                # 큐에 넣어주기
                qu.append(i)
            # 방문을 한 동그라미라면
            else:
            	# 서로의 색 비교해서 같으면 impossible로 한 뒤 break!
                if circles[circle_num] == circles[i]:
                    res = 'impossible'
        if res == 'impossible': break


T = int(input())

for _ in range(T):
    n, m = map(int, input().split())
    circles = [0] * (n+1)
    info = [[] for k in range(n+1)]
    # 양방향으로 데이터 받기
    for i in range(m):
        x, y = map(int, input().split())
        info[x].append(y)
        info[y].append(x)
	
    # 기본 값으로 possible
    res = 'possible'
    qu = deque()
    bfs(1)

	# 색칠 안된 것들도 있을 수 있으니 한번 더 bfs탐색 
    for i in range(n+1):
        if circles[i] == 0:
            bfs(i)

    print(res)