[백준] 1707번 이분 그래프

https://www.acmicpc.net/problem/1707

이분 그래프란?

이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다. (출처 : 위키백과)

=> 이분 그래프는 너비 우선 탐색을 활용하여 나열해놓고 깊이별로 색을 반복적으로 다르게 칠하면서 같은 색의 꼭지점끼리 연결되어있는 모순을 찾으면 된다.

나의 풀이

정점을 빨강색, 파랑색을 칠할 수 없으니 1, -1 을 반복적으로 부여한다. 깊이 우선 탐색으로 현재 정점에서 연결된 노드들의 visited 값을 -현재 depth의 값(마이너스 현재depth값)으로 지정하여 해결하였다.

import sys

K = int(sys.stdin.readline())
answer = []

def bfs(n):
    que = []
    que.append(n)
    check[n] = 1 // 첫 번째 depth는 1
    boolCheck = True
    while que:
        index = que.pop(0)
        for path in nodes[index]:
            if check[path] == 0: // 방문하지 않았을 떄
                que.append(path)
                check[path] = -check[index] // -(이전 depth값)을 부여
            if check[index] == check[path]: // 이미 방문 하였는데 현재 값과 다음 값이 같으면 false를 리턴
                boolCheck = False
    return boolCheck

for _ in range(K):
    V, E = map(int, sys.stdin.readline().split())

    nodes = [[] for _ in range(V+1)]
    check = [0 for _ in range(V + 1)]

    for _ in range(E):
        i, j = map(int, sys.stdin.readline().split())
        nodes[i].append(j)
        nodes[j].append(i)

    isTrue = True
    for i in range(1, V + 1):
        if check[i] == 0:
            if not bfs(i):
                isTrue = False
                break
    if isTrue:
        answer.append("YES")
    else:
        answer.append("NO")
print("\n".join(answer))