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

문제 보기

[사용한 알고리즘]

BFS(너비 우선 탐색)

 

[문제 접근]

집합 배정 정보를 관리하는 리스트를 선언한 후, 1번 정점부터 차례대로 연결된 정점들의 정보를 이용해서 집합을 배정합니다. 이후 2번 정점, 3번 정점... 마지막 정점까지 진행하면서 오류가 발생하면 NO를 출력, 끝까지 진행하면 YES를 출력하였습니다.

 

[알고리즘]

1. 1번 정점부터 집합 배정을 시작합니다.2. 해당 정점을 처음 방문하는 경우 1을 대입합니다. 이후 해당 정점과 연결된 정점들은 2를 배정하고, 그 정점들과 연결된 정점들은 1을 배정하는 BFS 탐색을 하였습니다. (만약 해당 정점을 방문한 적이 있다면 해당 정점의 값을 통해 연결된 정점들의 값을 대입하면 됩니다. 예를 들어 해당 정점이 1의 값을 가지면 연결된 정점들은 2로, 해당 정점이 2의 값을 가지면 연결된 정점들은 1을 대입합니다)3. 위 과정을 V번 정점까지 반복하며, 만약 중간에 모순이 발생하면 NO를 출력합니다.

 

 

[코드]

from collections import deque
import sys


def bfs(start):
    q = deque()
    q.append(start)
    bg[start] = 1  # 1구역 배정

    while q:
        v = q.popleft()
        for index in connect[v]:
            if bg[index] == -1:  # 아직 배정 x
                if bg[v] == 1:
                    bg[index] = 2
                elif bg[v] == 2:
                    bg[index] = 1
                q.append(index)
            elif bg[index] == bg[v]:
                return 0
    return 1


if __name__ == "__main__":
    k = int(sys.stdin.readline())
    for _ in range(k):
        v, e = map(int, sys.stdin.readline().split())  # 정점, 간선
        connect = [set() for _ in range(v + 1)]
        for _ in range(e):
            a, b = map(int, sys.stdin.readline().split())
            connect[a].add(b)
            connect[b].add(a)

        bg = [-1] * (v + 1)  # Bipartite Graph
        flag = True
        for i in range(1, v + 1):
            if bg[i] == -1:
                temp = bfs(i)
                if not temp:
                    flag = False
                    break

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