13265번 - 색칠하기

트리가 하나 주어졌을 때 이 트리를 두 가지 색으로 색칠할 수 있는지 묻는 문제입니다.
다만, 이어진 노드끼리는 같은 색을 띨 수 없습니다.

---

접근

일단 단순히 구현 문제라고 생각하고
노드를 모두 이진 트리로써 취급하여 생각해보기로 했습니다.
레벨 1에서는 빨간색, 레벨 2에서는 흰색, 레벨 3에서는 다시 빨간색 ... 이런씩으로 하여
만약 현재 탐색중인 노드와 탐색할 노드가 서로 이어져있는데 같은 색을 띈다, 이러면 두 가지 색으로 칠하지 못하고 만약 아니라면 두 가지 색으로 칠할 수 있습니다.

아마 그림으로 그려보면 이런 느낌이지 않을까 싶습니다...

---

선언

---

t = int(input())
que = deque()

for _ in range(t):
    ans = []
    que.clear()
    a,b = map(int,input().split())

일단 트리를 t만큼 받고 BFS 사용을 위해 que를 받아줍니다.
그리고 a,b로 트리를 받아주기 시작하겠습니다. que를 비우는 이유는 이따 상세히 서술하겠습니다.

    graph = [[0]*(a+1) for _ in range(a+1)]
    visited = [0]*(a+1)

그래프와 방문여부를 선언하고

    for _ in range(b):
        c,d = map(int,input().split())
        graph[c][d] = graph[d][c] = 1

이차원배열로 c노드와 d노드가 이어졌다는 형식으로 표현해줍시다.

    for i in range(1,d+1):
        if not visited[i]:
            ans.append(bfs(i))

그리고 노드중에 방문 안한 노드가 존재한다면 해당 노드는 bfs 탐색을 돌려줍니다.

---

BFS

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


def bfs(N):
    color = True
    visited[N] = 1
    graph[0][N] = color
    color = False
    que.append(N)

이 문제가 풀다보니 시간제한에 좀 민감한 친구여서 sysinput 선언해주고 시작하겠습니다.
어짜피 색은 두가지므로 True 와 False로 구분해주고 초기 색깔은 True로 지정해준 다음에 초기 색깔을 graph[0]에 넣어주겠습니다 (어짜피 안쓰는 자리, 형식상 인덱스 숫자 맞추려고 +1 선언해서 비는 공간). 그리고 노드 레벨 0은 탐색이 끝난거니까 color는 False로 바꿔주고 (다음 트리 레벨 넘어 갈 때 색 변경) 방문여부 1로 바꿔주고 que에 추가하면서 탐색을 시작합니다.

    while que:
        for _ in range(len(que)):
            connect = que.popleft()
            for i in range(len(graph[0])):

이번에도 이전 문제와 마찬가지로 BFS의 level을 파악해야 하므로 len(que)만큼만 for문을 돌려주겠습니다. 그리고 항상 탐색하듯이

                if not visited[i] and graph[connect][i] != 0:
                    visited[i] = 1
                    que.append(i)

만약 노드끼리 이어져있고 아직 방문을 안했으면 방문처리 하고 다음 탐색구간으로 지정해줍니다.

                    graph[0][i] = color

초반에 레벨 0에서 컬러를 바꾸고 for문에 들어왔으므로 color 변수 그대로 graph[0][i], 즉 다음 탐색지점의 색깔을 대입해주도록 합니다.

                if graph[connect][i] != 0:
                    if graph[0][i] == graph[0][connect]:
                        return 'impossible'

만약 탐색을 할 노드와 현재 탐색 중인 노드의 색깔이 일치한다면 impossible을 return 해주도록 합시다.
0이 아닐 때라는 조건을 건 이유는 만약 graph[0]의 인덱스의 초기값이 0인데 색깔이 아예 안들어있는 인덱스와 맞물리게 되면 조건식이 발동되는 대참사가 일어나므로 지정해줘야 합니다.

        if color == False:
            color = True
        elif color == True:
            color = False

마지막으로 해당 레벨의 색깔을 다 지정했으면 다음 레벨로 넘어갈 때 색깔을 변경해줍시다.

---

출력

    if 'impossible' in ans:
        print('impossible')
    else:
        print('possible')

최종적으로 ans배열에 impossible이 있다면 불가능, 없다면 가능을 출력해주면 끝납니다.

---

---

중요 실수

아까

for _ in range(t):
    ans = []
    que.clear()
    a,b = map(int,input().split())

에서 que.clear()를 해준 이유가 이게 BFS가 실행되다가 return을 만나면 굳이 while에 있는 que값을 다 빼고 나올 필요가 없기 때문에 que에 값이 잔류하게 됩니다.

그래서 이 상태로 que를 초기화시키지 않고 다시 BFS를 돌리면 값이 오염되서 이상한 결과가 나와버립니다. 이것때문에 상당히 시간을 허비해서 앞으로 코드를 짤 때는 이런 변수들 유심히 살펴야겠습니다.