[Baekjoon 1707 / python / 골드4] 이분 그래프

import sys

sys.setrecursionlimit(10 ** 9)

input = sys.stdin.readline

# 이분 그래프 판별 DFS 함수

def DFS(graph, start, visited, group):

    visited[start] = group

    for i in graph[start]:

        if visited[i] == 0:  # 방문 안 한 곳이라면

            result = DFS(graph, i, visited, -group)

            if not result: return False  # 하위에서 이분 그래프 아니라고 판단했다면 함수 종료

        elif visited[i] == group:  # 인접노드인데 그룹이 같을경우 이분그래프 아님

            return False

    return True

# 입력받은 갯수만큼 그래프를 검사한다

for _ in range(int(input())):

    # 사전준비

    N, E = map(int, input().split())  # 노드, 간선

    graph = [[] for _ in range(N + 1)]  # 연결정보

    for _ in range(E):

        a, b = map(int, input().split())

        graph[a].append(b)

        graph[b].append(a)

    visited = [0 for _ in range(N + 1)]  # 방문체크 리스트

    # 모든 노드에 대하여 DFS 진행

    for i in range(1, N + 1):

        if visited[i] == 0:  # 확인 안 한 노드가 있다면 진행

            result = DFS(graph, i, visited, 1)

            if not result: break

    print("YES") if result else print("NO")  # 이분 그래프면 YES, 아니면 NO 출력

 

DFS 또는 BFS를 사용해서 풀 수 있는 문제이다. 이분 그래프인지 확인 후 결과를 출력하면 된다.

 

이분 그래프는 어떤 노드와 그 인접 노드의 그룹을 각각 다르게 나눌 수 있는 그래프를 의미한다. 

이것을 알아내기 위해선, DFS 함수를 호출할 때 group값을 인자로 함께 주고 해당 노드의 인접 노드를 재귀호출 할 때 group값에 - 를 붙여서 -group으로 주면 현재노드와 인접노드의 그룹이 구분되게 된다.

 

group값은 visited 리스트에 넣는다. visited가 0이면(미방문이면) group값을 포함해 재귀호출하면 되고, visited가 0이 아니면 현재 노드와 인접 노드의 그룹값을 비교한다. 만약 group 값이 같으면 이분 그래프가 아니므로 즉시 False를 리턴하고 함수를 종료한다. 양방향 그래프이기 때문에 상위 노드에서 인접 노드를 호출할 때 한번, 인접 노드가 상위 노드를 호출할 때 각각 group값을 넣고 group값을 비교할 수 있게 된다.

 

또한 그래프가 끊어져 있을 수 있으므로, 모든 노드에 대하여 DFS를 진행해야 한다. visited 리스트에 0이 존재한다면 해당 노드를 시작 노드로 DFS를 다시 호출한다.