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

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

1707번: 이분 그래프

 

import sys
input = sys.stdin.readline


def setVerticesColor(start):
    global verticesColor

    todo = [start]
    verticesColor[start] = 1

    while todo:
        curVertex = todo.pop(0)

        for next in graph[curVertex]:
            if verticesColor[next] == 0:
                verticesColor[next] = verticesColor[curVertex]*-1
                todo.append(next)
            elif verticesColor[curVertex] == verticesColor[next]:
                return False

    return True


K = int(input())
for _ in range(K):
    V, E = map(int, input().split())
    graph = {i: [] for i in range(1, V+1)}

    for _ in range(E):
        e1, e2 = map(int, input().split())
        graph[e1].append(e2)
        graph[e2].append(e1)

    # -1: Red, 0: Undefined, 1: Blue
    verticesColor = [0 for _ in range(V+1)]
    isBipartiteGraph = True
    for v in graph.keys():
        if verticesColor[v] == 0:
            if setVerticesColor(v) == False:
                isBipartiteGraph = False
                break

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

 

이분 그래프는, 그래프를 탐색하면서 서로 다른 두 색을 반복해서 칠했을 때, 모든 edge에 걸친 2개의 vertex의 색이 다른 그래프를 말한다.

따라서 우리는 verticesColor라는 리스트에 각 vertex의 색상을 넣어준다. 0은 초기값, -1, 1은 각각 빨간색과 파란색이라고 한다.

 

먼저 setVerticesColor() 함수에 대해서 서술하자면, bfs 기반 함수이다. verticesColor을 참조하면서, todo라는 큐를 돌면서, 꺼낸 vertex의 인접 vertex를 graph에서 가져와 for문을 돌아준다. 만약 색이 정해지지 않았다면 이전과 다른 색으로 칠해주고 todo에 넣어준다. 만약 색이 정해져있는데, 이전과 같은 색을 띠고 있을 경우에는 False를 리턴해준다.

이런 식으로 todo에 대한 bfs 탐색이 끝났는데도 return False문을 만나지 않았다면 return True를 해준다.

 

이러한 setVerticesColor()를, 입력받은 모든 vertex를 돌면서, 해당 vertex가 아직 색칠되지 않았다면, 수행해준다. 여기서 중요한 것은, setVerticesColor(1)을 그냥 1번만 수행하는 게 아니라 모든 vertex에 대해서 setVerticesColor(v)를 수행했다는 것이다. 이렇게 하는 이유는, vertex들이 모두 이어져있다는 보장이 없기 때문이다.

 

마지막으로, isVipartiteGraph에 따라 출력 처리를 해주면 된다.