[백준] 1707번 - 이분 그래프

문제 분석

노드의 집합을 2개로 나누는데, 인접한 노드끼리 같은 집합이 되지 않도록 임의로 분할 할 수 있다고 한다.
잘 생각해보면 트리의 경우, 항상 이분 그래프가 된다는 것을 알 수 있다.
따라서 기존의 탐색 메커니즘에서 탐색한 노드에 다시 접근하게 됐을 때 현재 노드의 집합과 같으면 이분 그래프가 불가능하다는 것으로 판별할 수 있다.

접근 방법

1 입력된 그래프 데이터를 인접 리스트로 구현한다
2 모든 노드로 각각 DFS 탐색 알고리즘을 적용해 탐색을 수행한다. DFS를 실행할 때 현재 노드에서 연결된 노드 중 이미 방문한 노드가 나와 같은   집합이면 이분 그래프가 아닌것으로 판별한다. 실행 결과가 이분 그래프가니면 이후 노드는 탐색하지 않는다.
3 이분 그래프 여부를 정답으로 출력한다.
4 테스트 케이스의 개수만큼 과정 1 ~ 3을 반복한다

소스 코드

# 이분 그래프
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

K = int(input())
isEven = True


def DFS(idx):
    global isEven
    visit[idx] = True
    for value in arr[idx]:
        if not visit[value]:
            check[value] = (check[idx] + 1) % 2
            DFS(value)
        elif check[idx] == check[value]:
            isEven = False


for _ in range(K):
    node, edge = map(int, input().split())
    arr = [[] for _ in range(node + 1)]
    visit = [False for _ in range(node + 1)]
    check = [0 for _ in range(node + 1)]
    isEven = True

    for _ in range(edge):
        first, second = map(int, input().split())
        arr[first].append(second)
        arr[second].append(first)

    for i in range(1, node + 1):
        DFS(i)
    if isEven:
        print("YES")
    else:
        print("NO")