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

이번에 해결해 볼 문제는 백준에 있는 1707번 이분 그래프입니다.

---

문제 설명

• 주어진 그래프가 이분 그래프이면 YES, 이분 그래프가 아니라면 NO를 출력하면 되는 간단한 문제입니다.
• 그러나 이분 그래프를 모른다면 접근조차 못하는 어려운 문제입니다.
• 이분 그래프란?
  • 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프를 이분 그래프라 합니다.
  • 즉 간선으로 연결되어 있는 정점을 서로 다른 색으로 칠할 수 있으면 됩니다.

문제 해결 아이디어

• 이분 그래프를 확인하는 방법은 DFS와 BFS가 있습니다.
• DFS나 BFS를 통해 정점을 하나씩 탐색하가며 연결되어 있는 정점이 다른 색을 가지고 있는지 확인하면 됩니다.
• 저는 여기서 덜 복잡하고 계산 속도가 조금 더 빠른 BFS를 사용해 이분 그래프인지 확인했습니다.

문제 해결 코드

import sys
from collections import deque

input = sys.stdin.readline

K = int(input())
for _ in range(K):
    V, E = map(int, input().split())
    graph = [[] for _ in range(V + 1)]
    visited = [0] * (V + 1)
    for _ in range(E):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    # 탐색 시작
    result = "YES"
    for i in range(1, V + 1):
        if visited[i] == 0:
            q = deque([i])
            visited[i] = 1

            while q:
                v = q.popleft()

                # 연결된 정점
                for i in graph[v]:
                    # 아직 탐색되지 않은 정점은 현재 정점과는 다른 색으로 색칠
                    if visited[i] == 0:
                        visited[i] = 2 if visited[v] == 1 else 1
                        q.append(i)
                    # 탐색이 된 정점이라면 현재 정점과 다른 색인지 확인
                    elif visited[v] == visited[i]:
                        result = "NO"
                        q = deque([])
                        break
    print(result)