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

문제

이분 그래프

---

문제 해설

이분 그래프란 서로 연결된 두 노드가 각각 다른 색으로 색칠되어야 하는 그래프입니다. 이분 그래프는 이 색이 두가지로 제한 되어있습니다.

DFS와 BFS의 탐색 방식으로 풀 수 있는데, 탐색을 할 때 마다 현재 색칠되어있는 색깔과 반대되는 색깔인지만 확인하면 됩니다.

DFS로 풀 때 v x v 형식의 매트릭스를 사용하면 메모리 초과가 나고, 일반적으로 풀어도 recursionError가 뜨기 때문에 깊이 제한을 풀어야 합니다.
웬만하면 bfs로 푸시는 것을 권장합니다.

---

풀이 코드

import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
k = int(input())


def dfs(v, group):
    coloring[v] = group
    for x in connect[v]:
        # 색칠 안되있으면 dfs 진행
        if coloring[x] == 0:
            # 만약 그룹이 다른게 하나라도 존재하면 연쇄로 False 리턴
            if not dfs(x, -group):
                return False
        # 색칠 되있으면 확인
        else:
            # 그룹이 다르다 -> False 리턴
            if coloring[x] == coloring[v]:
                return False
    return True


# 틀린 이유 1. 1번 노드에서만 탐색함 -> 1번노드가
# 다른 노드와 연결 안되있으면 NO 출력
# 결국 1번노드부터 끝까지 전부 dfs 돌려야함
for _ in range(k):
    v, e = map(int, input().split())
    connect = [[] for _ in range(v + 1)]
    coloring = [0] * (v + 1)
    # 연결 정보
    for _ in range(e):
        a, b = map(int, input().split())
        connect[a].append(b)
        connect[b].append(a)
    flag = True
    for i in range(1, v + 1):
        if coloring[i] == 0:
            flag = dfs(i,1)
            if not flag:
                break
        
    print("YES" if flag else "NO")

---