백준 #13265 색칠하기

코드

import sys
# sys.stdin = open("input.txt")
input = sys.stdin.readline
from collections import deque


def bfs(start):
    global check
    q = deque()
    q.append(start)
    color[start] = 0

    while q:
        cur = q.popleft()
        for node in arr[cur]:
            if color[node] == -1:
                color[node] = (color[cur] + 1) % 2
                q.append(node)
            else:
                if color[node] == color[cur]:
                    check = True



T = int(input())
for _ in range(T):
    n, m = map(int, input().split())
    arr = [[] for _ in range(n + 1)]
    color = [-1] * (n + 1)
    for _ in range(m):
        a, b = map(int, input().split())
        arr[a].append(b)
        arr[b].append(a)
    check = False
    for i in range(1, n + 1):
        if color[i] == -1:
            bfs(i)
            if check:
                break

    if check:
        print("impossible")
    else:
        print("possible")

풀이

오늘부터 오전 알고리즘 스터디를 시작했다!! 무려 오전 8시부터 진행!!! 첫날이라 그런지 머리가 안돌아갔다(핑계) 위 문제를 결국 시간안에 못풀었는데 단순 이중 for문으로 해결 가능하다고 생각했었다. 하지만 최대한 안겹치게 색을 칠해주려면 먼저 이어져 있는 노드들부터 색을 채워나가야하기 때문에 bfs로 푸는게 맞았다. 스터디 첫날이였는데 다들 좋으신분 같다! 내일도 파이팅!!