백준(BOJ) 13265 색칠하기(Python)

문제 내용

 

BFS 문제.

아주 전형적인 BFS 문제로, visited 배열의 케이스를 0,1,2로 나눠서 진행했다.

0이면 방문하지 않음, 1, 2는 원의 색으로 설정했다.

완전 그래프라는 보장이 없기 때문에 모든 점에 대해서 BFS를 돌려줘야 한다.

 

코드는 다음과 같다.

 

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

t=int(input())
for i in range(t):
    n,m=map(int,input().split())
    D={i:[] for i in range(n+1)}
    for j in range(m):
        x,y=map(int,input().split())
        D[x].append(y)
        D[y].append(x)
    queue=deque()
    visited=[0 for i in range(n+1)]
    for j in range(1,n+1):
        if not visited[j]:
            queue.append([j,1])
            visited[j]=1
            while queue:
                x,c=queue.popleft()
                flag2=0
                for i in D[x]:
                    if not visited[i]:
                        visited[i]=c+1
                        queue.append([i,(c+1)%2])
                    else:
                        if visited[i]!=c+1:
                            flag2=1
                            break
                if flag2:
                    break
        if flag2:
            break
    if flag2:
        print('impossible')
    else:
        print('possible')

 

오늘 좀 문제가 안 풀린다.

5문제 정도 건드려봤는데 푼 게 없었다.

문제들이 잘 안 풀리니 멘탈이 터져서 쉬운 것도 잘 못 풀겠더라.

아직 많이 부족하다.