[백준] 1707: 이분 그래프 python 구현 / BFS, Bipartite Graph, 반례 집합

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

• 그림으로 표현

풀이

이분 그래프 문제를 해결하기 위해서는 먼저 이분 그래프(Bipartite Graph)가 무엇인지에 대해 선행되어야 한다.

출처: https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

이분 그래프란, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어져 있는 (= 같은 그룹에 속한 정점끼리는 서로 인접하지 않도록 하는) 그래프를 이분 그래프라고 한다.

이를 판별하기 위해서는, 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있다면 이를 이분그래프로 정의할 수 있다.

 

우리의 문제에 비추어 보자면, 인접한 정점을 서로 다른 색으로 칠했을 때, 1번 테스트 케이스는 가능하지만, 2번 테스트 케이스의 경우 4번 노드에서 불가능 함을 두 색상이 겹치는 것을 확인 할 수 있다.

 

BFS 를 이용한 이분 그래프 판별

1. BFS로 탐색하면서 정점을 방문할 때 마다, 두 가지 색 중 하나를 칠한다.
2. 다음 정점을 방문하면서 자신과 인접한 정점은 다른 색으로 칠한다.
3. 탐색을 진행할 때, 자신과 인접한 정점의 색이 자신과 동일하다면, 이분 그래프가 아니다.
4. 모든 정점을 방문했을 때 문제가 없다면, 이분 그래프이다.

 

추가로 유용한 반례를 모아놓은 게시글을 공유한다. 해당 페이지에는 반례와 함께 체크해야할 부분이 같이 적혀있어 유용했다 ! 

나의 경우, 그래프의 정점이 모두 연결된 경우만 생각하였다. 그래서 그래프 탐색이 필요한 이유의 반례에 대한 오답률이 높았다.

• https://www.acmicpc.net/board/view/107653

CODE

import sys
from collections import deque

def odd_even(n):
    return 1 if n % 2 == 0 else -1

def bfs(current):
    queue = deque()
    level = 0
    queue.append((current, level+1))
    vst[current] = odd_even(level) # 깊이에 따라, 서로 다른 색상을 칠해준다. (인접한 정점 끼리는 같은 색상)

    while queue:
        now = queue.popleft()
        c_node, level = now

        for i in adj_list[c_node]:
            # 방문한 적이 없다면 두 색상 중 하나로 칠해준다.
            if not vst[i]:            
                queue.append((i, level+1))
                vst[i] = odd_even(level)

            # 방문한 적이 있고, 현재 칠하려는 색상과 같으면 pass
            elif vst[i] == odd_even(level):
                continue

            # 방문한 적이 있고, 현재 칠하려는 색상과 다르다면, 인접리스트가 아니다.
            elif vst[i] != odd_even(level):
                return False

    return True


k = int(input())
result = []
for _ in range(k):
    vertex, edge = map(int, input().split())
    adj_list = [[] for _ in range(vertex+1)]
    for _ in range(edge):
        u, v = map(int, sys.stdin.readline().split())
        adj_list[u].append(v)
        adj_list[v].append(u)
    
    vst = [0]*(vertex+1)

    # 그래프의 정점이 서로 이어지지 않았을 수 있음 (두개의 그래프 존재 가능성)
    graph_list = []
    for i in range(1, vertex+1):
        if not vst[i]:
            graph_list.append(bfs(i))

    if all(graph_list):
        result.append('YES')
    else:
        result.append('NO')

for i in result:
    print(i)

Reference

• https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html