[BOJ][🟡4][백준#01707] 이분 그래프

문제 출처

BAEKJOON Online Judge #1707

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다. 

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

제한

2 ≤ K ≤ 5 1 ≤ V ≤ 20,000 1 ≤ E ≤ 200,000

예제

입력

2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2

출력

YES
NO

My Sol

import sys
input = sys.stdin.readline
from collections import deque

def check():
    V, E = map(int, input().split())
    D = [2] * V
    G = [[] for _ in range(V)]
    for _ in range(E):
        u, v = map(int, input().split())
        G[u-1].append(v-1)
        G[v-1].append(u-1)

    for s in range(V):
        if D[s]==2:
            Q = deque()
            Q.append(s)
            D[s] = 0
            ql = 1

            cnt = 1
            while Q:
                for _ in range(ql):
                    u = Q.popleft()
                    ql -= 1
                    for v in G[u]:
                        # v 값이 초기값인 2일 때
                        if D[v]==2:
                            D[v] = cnt
                            Q.append(v)
                            ql += 1
                            continue

                        # D[v] 값이 cnt와 같다면 'False' return
                        if D[v]==cnt^1:
                            return 'NO'
                cnt ^= 1
    return 'YES'

T = int(input())
for _ in range(T):
    print(check())

이분 그래프?

이분그래프의 개념을 처음 알게 된 문제였다. 이분그래프에 대한 문제의 설명이 간결하고 함축되어 있어 이해를 하지 못해 검색을 통해 개념을 알게 되었다. 예를 들어 어떤 정점을 파란색으로 칠할 때, 해당 정점과 인접한 정점은 빨간색으로 칠해나간다. 이렇게 모든 정점을 빨간색과 파란색으로 칠해가는 과정에서 어떤 파란색 정점에 인접한 정점이 이미 파란색으로 색칠되었다면, 이는 이분 그래프가 아닌 것이다.

풀이

위에서의 빨간색과 파란색을 각각 0과 1로 체크하였고, 그래서 초기화를 2로 하였다. 1과 0의 반전은 비트를 이용하였으며, BFS 방식으로 문제를 해결했다. for문을 이용해 0부터 V-1까지의 정점 번호 v에 대해 D[v]가 2라면, 아직 방문하지 않은 정점이므로 BFS를 돌려주는데, BFS는 위의 방식대로 정점이 2라면 해당 level의 cnt를 입력해주고, Q에 다시 넣는 것이고, 2이 아닌 체크된 정점이라면 정점과 같은 체크가 아닌지 확인하여 같은 체크라면 바로 NO를 반환해 출력하도록 한다.

처음에 채점 진행 중에 틀리고 말았는데, 이는 모든 정점이 이어져있는 연결 그래프라고 오인했던 점에서 발생한 오류했다. 단순히 시작점을 0으로 하면 모든 정점을 체크할 것이라고 생각했고, 이를 개선하기 위해 for문을 이용해 방문하지 않은 정점에서 다시 BFS를 돌려주는 방식을 사용했다.

결과

맞았습니다!!