13265 백준 파이썬

바보같이 코드 짜서 괜히 엄청 해맸던 문제

일단 한 점의 색깔을 임의로 지정하고, 인접한 점들을 모두 변경해줘야 하기떄문에 dfs보다는 bfs가 나을 것이다.

그래서 코드를 짰는데, 바보처럼 bfs(1)을 실행시켰다.

이러면 1이 독단적으로 떨어져 있는 경우, 코드가 실행이 안된다. 괜히 keyError가 나서 도대체 뭐지 싶었다.

정답코드

#https://www.acmicpc.net/problem/13265
import sys
from collections import deque
input=sys.stdin.readline
def bfs(start):
    global impossible
    q=deque()
    if vis[start]=="B":
        origin="B"
        op="W"
    else:
        origin="W"
        op="B"
    for x in connection[start]:
        if vis[x]==0:
            q.append(x)
            vis[x]=op
        elif vis[x]==origin:
            impossible=1
            return
    while q:
        bfs(q.popleft())

t=int(input())
for _ in range(t):
    connection=dict()
    impossible=0
    n,m=map(int,input().split())
    vis=[0 for _ in range(n+1)]
    for _ in range(m):
        x,y=map(int,input().split())
        if x!=y:
            if connection.get(x):
                connection[x].extend([y])
            else:
                connection[x]=[y]
            if connection.get(y):
                connection[y].extend([x])
            else:
                connection[y]=[x]
    if connection:
        for x in connection.keys():
            if vis[x]==0:
                vis[x]="B"
                bfs(x)
        if impossible==1:
            print("impossible")
        else:
            print("possible")
    else:
        print("possible")