[백준 1707] 이분 그래프(Python)

1. 요약

주어진 그래프가 이분 그래프인지 아닌지 확인하는 문제.
이분 그래프의 의미는 다음과 같다.

• 2개의 집합이 주어져 있을 때, 동일한 소속에 있는 정점끼리는 서로 인접하면 안된다.

2. 아이디어

우선 문제를 풀다가 막히시는 분이 있다면 https://www.acmicpc.net/board/view/28396 을 참고하면 된다.

일단 그래프가 완성될때까지 정점을 집합에 두면 안된다. 다시 말해, 그래프를 완성하고 난 후, 정점을 BFS를 이용하여 어떤 집합에 속해야하는 지 정한다. 예를 들어 현재 정점이 집합 A에 속해있으면, 인접한 다른 정점들은 집합 B에 둔다. 만약 인접한 다른 정점의 집합이 이미 정해져있으면, 현재노드가 속한 집합과 인접한 노드가 속한 집합을 비교한다. 만약 같으면, 이분그래프가 아니다.

주의할 점은 주어진 그래프가 연결그래프가 아니므로, 각 정점을 시작점으로 둔다. 만약 시작점에 있는 노드가 어떤 집합에 소속되지 않는다면, 집합에 소속 할 수 있도록 한다.

3. 코드

import sys
from collections import deque

tc = int(sys.stdin.readline().rstrip())

def solve():
    v, e = map(int, sys.stdin.readline().rstrip().split())
    connect = [[] for _ in range(v+1)]
    q = deque()
    visited = [False for _ in range(v+1)]
    house = {}

    for i in range(1, v+1): q.append(i)

    for _ in range(e):
        v1, v2 = map(int, sys.stdin.readline().rstrip().split())
        connect[v1].append(v2)
        connect[v2].append(v1)

    for node in range(1, v+1):
        if node not in house.keys(): house[node] = 'A'
        q = deque()
        q.append(node)

        while q:
            cur_node = q.popleft()
            for next_node in connect[cur_node]:                
                if cur_node == next_node: continue
                if not visited[next_node]:
                    visited[next_node] = True
                    if house[cur_node] == 'A': house[next_node] = 'B'
                    else: house[next_node] = 'A'
                    q.append(next_node)
                
                elif house[cur_node] == house[next_node]: return False

    return True


while tc:
    if solve(): print('YES')
    else: print('NO')
    tc -= 1