백준 / 1707 이분 그래프 python3

www.acmicpc.net/problem/1707

1707번: 이분 그래프

이분 그래프에 대해 이 문제를 통해 알게 되었습니다.

 

이분 그래프는 그래프의 정점을 두 집합으로 분할할 때, 같은 집합 내의 노드끼리는 인접하지 않도록 (간선이 연결되어있지 않도록) 분할할 수 있으면 이분 그래프라고 합니다.

 

이분 그래프는 두 가지 색을 이용해 판별할 수 있습니다.

빨강, 파랑 두 가지 색으로 판별한다고 합시다. 그래프의 첫 노드를 빨강으로 칠하고, 그 노드와 인접 노드는 파랑으로 칠합니다. 이 과정을 반복하며, 인접 노드에 같은 색이 칠해진다면 이분 그래프가 될 수 없습니다. 마찬가지로 같은 부모 노드를 가지고, 같은 레벨 (뎁스)의 노드가 다른 색이어도 이분 그래프가 될 수 없습니다. 

 

 bfs를 이용하여 이분 그래프인지 판별하였고 다음과 같이 판별할 수 있습니다. (dfs도 유사한 방법으로 하면 됨)

 

1. 그래프를 탐색하면서 정점을 방문할 때마다 체크를 했다면 패스, 안 했다면 두 가지 색 중 인접 노드(부모노드)와 다른 색을 칠한다.

2. 새로 체크를 했다면 queue에 해당 노드를 넣는다. 

3. 인접 노드가 같은 색이면 이분 그래프가 되지 않는다.

4. 다 통과하면 이분 그래프이다.

 

코드는 다음과 같습니다.

from sys import stdin
T = int(stdin.readline())

for _ in range(T):
    V, E = map(int,stdin.readline().split())
    arr = [ [] for _ in range(V+1)]
    check = [0 for _ in range(V+1)]
    result = "YES"
    
    for _ in range(E):
        From, To = map(int, stdin.readline().split())
        arr[From].append(To)
        arr[To].append(From)
    
    # 이분 그래프인지 판단
    # 색을 1, -1로 구분하여 탐색하면서 합이 0이 아니면
    # 1,1 or -1,-1 이므로 이분 그래프 X
    queue = []
    for i in range(1,len(arr)):
        # check 한 경우
        if check[i] != 0:
            continue
        
        if result == "NO":
            break
        
        queue.append(i)
        check[i] = 1
        
        while(len(queue) != 0):
            x = queue[0]
            queue.pop(0)
            
            if result == "NO":
                break
            
            for node in arr[x]:
                # 인접 노드 체크 X
                if check[node]==0:
                    if check[x]==1:
                        check[node]= -1
                    else:
                        check[node] = 1
                    queue.append(node)
                # 인접 노드 체크 O
                # 합이 0 아니면 이분 그래프 X
                else:
                    if (check[node]+check[x]) != 0:
                        result = "NO"
                        break
                    
    print(result)