[백준 1707] 이분 그래프 Python

📘 문제 정보

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

 

📝 문제 해석

• 하나의 무방향 그래프에서 모든 정점을 두 개의 집합으로 나누되, 같은 집합 내의 정점들 사이에는 간선이 없어야 하는 조건을 만족하면 이 그래프를 이분 그래프(Bipartite Graph) 라고 한다.
• 입력으로 주어지는 여러 개의 무방향 그래프 각각에 대해 이 조건을 만족하는지를 판별해야 한다.

 

💡 풀이 아이디어

그래프를 두 가지 수(예: 1, 2)로 방문처리하며, 인접한 노드끼리는 다른 수가 되도록 만든다. 이 과정을 BFS로 수행하되, 이미 수가 정해진 정점과 인접한 정점을 다시 방문할 때, 수가 같다면 이분 그래프가 아님을 판별한다.

 

✅ 핵심 전략

• 방문처리를 위해 visited 배열을 0(미방문), 1 또는 2로 구성
• BFS 탐색 중 현재 노드가 1이면 인접 노드는 2, 2이면 1로 체크
• 이미 방문한 노드인데 인접 노드와 수가 같다면 flag = False
• 모든 정점에 대해 BFS를 수행 (그래프가 연결되어 있지 않을 수 있으므로)

# pypy3

import sys
sys.setrecursionlimit(100000)
from collections import deque
input = sys.stdin.readline

k = int(input())
for _ in range(k):
    v, e = map(int, input().split())
    arr = [[] for _ in range(v+1)]
    for _ in range(e):
        a, b = map(int, input().split())
        arr[a].append(b)
        arr[b].append(a)

    flag = True
    queue = deque([])
    visited = [0] * (v+1)
    for i in range(1, v+1):
        if visited[i] == 0:
            queue.append(i)
            visited[i] = 1
            while queue:
                if not flag:
                    break

                x = queue.popleft()
                for nx in arr[x]:
                    if visited[nx] == 0:
                        queue.append(nx)
                        visited[nx] = visited[x]%2+1
                    else:
                        if visited[nx] == visited[x]:
                            flag = False

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