[백준 파이썬] 1707 이분 그래프

📌문제 출처

백준 단계별 문제풀이 - 그래프와 순회
https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

❓ 문제

 

❗ 풀이

• stack, bfs 활용

📗 풀이 코드

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

def is_bps(n): # node n이 포함된 그래프의 이분 그래프 여부 확인
    set_no = 1 # 노드 n이 포함될 집합, 계속 변경될 값
    bps[n] = set_no # node n은 첫번째 집합(1)에 담기. 두번째 집합이면 -1
    stack = deque([[i,-set_no] for i in tree[n]]) # root node부터 연결된 [node,들어갈 집합] stack
    while stack : # 하나의 root node로부터 연결된 모든 node 확인
        node,tmp_set_no = stack.popleft() # node를 하나씩 꺼내서
        if not bps[node] : # 아직 확인하지 않은 node라면
            bps[node] = tmp_set_no # 상위 node와 반대 집합으로 넣기
            for i in tree[node]: # 최초 방문한 node의 자식 node에 대해
                stack.append([i,-tmp_set_no]) # [node,집합] 넣기
        elif bps[node] != tmp_set_no : # 현재 집합이 들어갈 집합과 다르면
            return False # 이분 그래프 불가
    return True

for _ in range(int(input())):
    v,e = map(int,input().split())
    tree = defaultdict(list) # 각 node:[이어진 노드]
    bps = defaultdict(int) # node 별로 두 집합(-1,1)에 나눠서 담을 것임 초기엔 0
    for _ in range(e):
        a,b = map(int,input().split())
        tree[a].append(b)
        tree[b].append(a)

    flag = True
    for i in range(1,v+1) : # 모든 노드에 대해 이분 그래프 성립 확인
        if flag :
            if not bps[i] :
                flag = is_bps(i)
        else :
            print('NO')
            break
    else :
        print('YES')

📗 코드 해설

• tree라는 dictionary에 부모노드 : [자식노드들]로 연결된 노드들을 모두 담아둔다.
• bps라는 dictionary에는 각 노드별 이분 집합을 넣어줄 것이다.
• 이후 모든 노드들에 대하여 이분 그래프가 성립하는지 확인한다.
• is_bps()라는 함수를 생성한다.
  해당 함수에서는 n이라는 root node를 시작해서 n과 연결된 node들이 n과 다른 집합에 들어갈 수 있는지 확인하고,
  n의 자식 node들의 자식 node들이 그들의 부모 node와 다른 집합에 들어갈 수 있는지 확인하는 함수이다.
• is_bps(n) 함수를 시작할 때는 node n의 집합은 1(set_no)에 들어가도록 만든다.
  그리고 bps 또한 set_no로 지정해준다. stack에는 node n의 자식 node와 자식 node들이 들어갈 집합(-set_no로 부모 node와 반대의 집합)을 list형태로 넣어준다.
• bfs를 진행하면서 확인하지 않은 node 라면 bps[node]를 부모 node의 반대 집합에 넣어주고,
  그 node의 자식 node들과 들어가야할 집합을 stack에 넣어준다.
• 이미 방문한 node이지만 들어가야할 집합의 반대에 이미 들어가있다면 이분 그래프가 불가능하므로 false를 반환한다.
• 모든 bfs가 끝났다면 이분 그래프가 성립하므로 True를 반환한다.