[BOJ 1707] 이분 그래프 (Python)

풀이

처음 이분 그래프의 개념에 대해 잘 몰라 헤맸던 문제이다. 아래는 이분 그래프를 표현한 그림이다.

사진 출처 : 링크

그림처럼 시작하는 정점에 연결된 간선을 따라 이어진 정점들을 하나씩 탐색하면서 색을 바꿔가며 칠했을 때, 같은 색끼리는 간선이 없는 경우를 이분 그래프라고 한다. 즉, 포인트는 인접된 두 정점을 서로 다른 색으로 칠할 수 있는지 없는지를 판단하는 것이다. 아래 그림(백준 문제에서 주어진 2번째 테스트 케이스)을 보면 이해하는데 도움이 될 것이다.

코드

import sys

input = sys.stdin.readline
K = int(input())
RED, BLUE = 1, -1
sys.setrecursionlimit(10 ** 6)
# 백준에서 재귀의 깊이 제한이 1000 이라고 함.
# 재귀 제한을 설정해주지 않으면 recursionError 가 발생함. 따라서 재귀 제한을 설정해줬음. 


def dfs(vertex, color):
    global flag
    colors[vertex] = color  # 시작 정점 color 색으로 칠함.
    
    # 인접한 정점들 중에서
    for graph in graphs[vertex]:
        # 인접한 정점의 색상이 같으면 이분 그래프 X 이므로 종료
        if colors[graph] == color:
            flag = False
            return
        # 정점을 칠한적이 없으면 재귀 함수 호출
        if colors[graph] == 0:
            dfs(graph, -color)


for i in range(K):
    V, E = map(int, input().split())

    graphs = [[] for _ in range(V + 1)]   # 연결리스트 그래프
    colors = [0] * (V + 1)   # 색상 저장
    flag = True
    for _ in range(E):
        x, y = map(int, input().split())
        graphs[x].append(y)
        graphs[y].append(x)

    for v in range(1, V + 1):
        if not flag:
            break
        if colors[v] == 0:
            dfs(v, RED)   # 처음에 빨간색으로 칠함. (파란색으로 먼저 칠해도 상관 X)

    print('YES' if flag else "NO")