파이썬 알고리즘 269번 | [백준 1707번] 이분 그래프-bfs

269. 이분 그래프

1) 어떤 전략(알고리즘)으로 해결?

• bfs, dfs

2) 코딩 설명

• 이분그래프를 이해하는 것이 오래걸리는 문제였다

<내 풀이>

출처 : 출처

from collections import deque
import sys
k=int(sys.stdin.readline().strip())

def bfs(start) :    
    q=deque()
    q.append(start)
    visit[start]=2 # 처음은 2 
    while q :
        now = q.popleft()
        
        for chk in graph[now]:
            if visit[chk]==-1 : 
                q.append(chk)
                visit[chk] = -visit[now] 

                # 지금 아이와 반대 색깔로 넣어주기
            else : 
                if visit[chk]==visit[now] :
                    return False
    return True

for test in range(k) :

    v,e = map(int, sys.stdin.readline().strip().split())
    graph = [[] for _ in range(v+1)]
    visit = [-1 for _ in range(v+1)]
    possible = True
    for _ in range(e) :
        u,v = map(int, sys.stdin.readline().strip().split())
        graph[u].append(v)
        graph[v].append(u)
    
    for i in range(1,v+1) : 
        if visit[v]==-1 : 
            possible = bfs(i)
        if possible==False:
            break
    if possible : print("YES")
    else : print("NO")

<반성 점>

• 단순 bfs, dfs 에서 조금만 더 꼬아서 문제를 내면, 의도를 파악하지 못하고 마냥 어려워하는 나의 모습이 너무 아쉽다.
• bfs, dfs에서 모두 조금씩 꼰 것에 불가하니~ 너무 겁먹지 말고 문제를 파악할 수 있도록 해보자