백준 1707 이분그래프 파이썬

 

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

1707번: 이분 그래프

 

 

이분 그래프가 어떤 그래프인지 문제에 있는 설명으로 알 수가 없어, 검색을 하고 풀었다.문제의 핵심은 전체 그래프가 2개의 그룹으로 나누어 질 수 있는지 보면 된다. 예를 들어 처음 탐색을 시작하는 그래프의 그룹을 1이라고 가정하면, 그 다음으로 탐색 되는 그래프의 그룹은 2가 된다. 그리고 그 다음으로 탐색 되는 그래프의 그룹은 1이 된다. 이 경우를 만족하는지를 판별하면 된다.

 

 

1. 모든 노드에 대해 그래프 탐색을 한다.
2. 분기 필요
   1. 현재 노드가 이전에 그룹핑 되었다면(1,2) 탐색하지 않는다. → 종료
   2. 현재 노드가 이전에 그룹핑 되지 않았다면(0)이면 탐색한다.
3. 시작하는 노드를 1로 주고, BFS 탐색을 한다.
4. 다음 그룹값을 구한다(현재 그룹값이 1이면 2, 현재 그룹값이 2이면 1로 변환)
5. 분기 필요
   1. 다음 탐색할 노드의 그룹값이 0이면, 다음 그룹값을 넣어주고, 다음 노드를 기준으로 계속 탐색한다.
   2. 다음 탐색할 노드의 그룹값이 0이 아니면 추가 판별이 필요하다 (분기 필요)
      1. 다음 탐색할 노드에 들어있는 노드값이 현재 노드 그룹값과 동일하다면 실패이므로 False를 반환한다. → 종료
      2. 다음 탐색할 노드에 들어있는 노드값이 현재 노드 그룹값과 다르다면 실패조건이 아니므로, 이 노드를 빼고 계속 탐색한다.
6. 위의 방식으로 모든 노드를 살펴본 후, 한번이라도 False가 발생하면 이 그래프는 이분 그래프가 아니다. 모두 True인 경우 이 그래프는 이분 그래프다.

 

import sys
from collections import deque

def getNextValue(value):
    if value == 1 :
        return 2
    if value == 2 :
        return 1

def sol(start_node):
    que = deque()
    que.append((start_node, 1))
    node_group[start_node] = 1

    while que :
        now_node, now_group = que.popleft()

        for next_node in node[now_node]:
        
        if node_group[next_node] == now_group:
                return False
        
        if node_group[next_node] == 0 :
                next_value = getNextValue(now_group)
                node_group[next_node] = next_value
                que.append((next_node,next_value))

    return True



k = int(sys.stdin.readline().rstrip())
for _ in range(k) :
    
    #입력 처리
    v,e = map(int,sys.stdin.readline().split())
    node = [[] for _ in range(v+1)]
    node_group = [0 for _ in range(v+1)]

    for _ in range(e) :
        a,b = map(int,sys.stdin.readline().split())
        node[a].append(b)
        node[b].append(a)


    #Solution
    yes_flag = True
    for start_node in range(1,v+1):
        if node_group[start_node] == 0:
            yes_flag = sol(start_node)
        if not yes_flag:
            break
    if yes_flag :
        print("YES")
    else:
        print("NO")