[백준] 1707번 - 이분 그래프 (파이썬) 문제 및 풀이

문제) 백준 - 그래프 이론 (Graphs) - 이분 그래프

-> acmicpc.net/problem/1707

1707번: 이분 그래프

 

그래프가 주어졌을 때, 집합을 둘로 나누어 한 집합에 속한 정점끼리는 인접하지 않게 분할하는 문제. 처음에 주어진 그래프가 당연히 연결 그래프일거라 생각해 약 2시간가량 맞왜틀(맞는데 왜 틀려)를 시전 했다. 연결 그래프가 아니어도 이분 그래프가 될 수 있음을 깨달았다.

 

그래프를 인접 리스트 형태로 선언하고, 각 노드가 어떤 집합에 포합 되는지 확인하기 위해 div 리스트를 정점만큼 선언한다.

div의 값이 -1인 경우 방문하지 않았거나, 인접 노드가 없는 경우이고 0 또는 1인 경우 각 집합에 포함된다.

그래프를 탐색하기 위해 bfs를 이용한다. bfs로 탐색하면서 인접 노드로 이동할 때 이전 노드에 저장된 div값과 반대로 div값을 대입한다.

div값이 -1이 아닐 경우에는 이미 다른 노드에서 한 번 거쳐간 것이다. 이럴 때는 이전 노드와 현재 노드의 div값을 비교하여 만약 다를 경우 continue 하고 아닐 경우 이분 그래프가 불가능하다.

 

Ex)예제 입력:4 41 22 33 44 2

Node	1	2	3	4
div	0	1	0	0

노드가 3번, 4번 일 때 주목하자. 서로 연결되어 있지만 같은 집합에 들어가게 되므로 우리는 이분 그래프가 불가능한 것을 알 수 있다.

 

그 후, 주어진 그래프가 연결 그래프가 아니므로 v개의 모든 노드에 대해 검사한다. 

 

 

 

 

소스 코드)

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

testcase = int(input())
def bfs(start, graph, div):
    global ans
    queue = deque()
    queue.append(start)
    div[start] = 0
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if div[i] == -1:
                div[i] = 1 if div[v] == 0 else 0
                queue.append(i)
            else:
                if div[i] != div[v]:
                    continue
                else:
                    ans = False


for _ in range(testcase):
    v, e = map(int, input().split())
    graph = [[] for _ in range(v + 1)]
    div = [-1] * (v + 1)
    
    for _ in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    ans = True
    for i in range(1, v):
        if div[i] == -1:
            bfs(i, graph, div)
        
    if ans:
        print("YES")
    else:
        print("NO")