파이썬 백준 1707번 : 이분 그래프

문제

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

 

 

 

풀이

 

https://en.wikipedia.org/wiki/Bipartite_graph

이분 그래프란 위와 같이 서로 인접한 노드를 다른색으로 칠할때, 두가지 색으로만 칠할 수 있는 경우를 의미한다. 

따라서 모든 노드를 탐색하며 자신의 부모와 다른 색으로 칠할 수 있는지를 확인하며 풀이했다.

 

• 알고리즘 BFS
• 자료구조 인접리스트, deque

color리스트로 visited의 기능을 대신한다. 초기는 모두 0으로 되어있고, 1,-1가 두가지 색이라고 가정한다.

BFS를 이용하여 정점을 탐색하며, 색이 칠해지지 않은 경우 부모의색* -1로 칠하고, 칠해져 있는 경우 그 색이 무엇인지 확인한다. 색이 부모와 같은 경우는 이분 그래프가 아님으로 그 즉시 NO를 return한다. (부모와 다른색으로 칠해져있는경우 별다른 action을 취하지않아도된다(이미방문)) 

 

import sys
from collections import deque

def BFS(node):
    queue=deque()
    queue.append(node)
    color[node]=1

    while queue:
        v=queue.popleft()
        for child in Graph[v]:
            if color[child]==0: #색이 칠해지지 않은 상태이면
                color[child]=color[v]*-1 #부모와 다른 색으로 칠하고(방문처리)
                queue.append(child) #queue에 넣음
            else: #색이 이미 칠해져있는 상태일때
                if color[child]==color[v]: #색이 부모와 같다면 -> 이분그래프가 아님!
                    return "NO" # NO return
    return "YES" 



K=int(sys.stdin.readline())
for _ in range(K):
    V,E=map(int,sys.stdin.readline().split())
    Graph=[[] for _ in range(V+1)]
    color=[0]*(V+1)

    ### 그래프 만들기(인접리스트) ###
    for _ in range(E):
        v1,v2=map(int,sys.stdin.readline().split())
        Graph[v1].append(v2)
        Graph[v2].append(v1)

    ### BFS로 순회하면서 색 칠하기 ###
    for i in range(1,V+1):
        if color[i]==0:
            result=BFS(i)
            if result=="NO": #result가 NO이면 즉시 종료
                break
    print(result)