[Algorithm] 이분그래프(Bipartite Graph) ( + BOJ1707 )

 

이분 그래프(Bipartite Graph)란,  서로 다른 두 집합의 노드 간 연결로 이루어진 그래프이다. 같은 집합의 노드 사이에는 간선이 존재하지 않는다.  예를 들어, 사람-취미 관계를 나타내는 그래프라고 해보자. 

 

 

 

 

위 그래프의 노드는 사람집합, 취미집합 두 가지로 나뉜다. 관계를 나타내는 간선은 사람과 집합 사이에 있어야 한다. 사람과 사람, 취미와 취미 사이에 간선이 있어서는 안 된다. 이렇듯, 이분 그래프는 서로 다른 집합 사이의 네트워크를 나타낼 때 사용된다. 연령별 선호 영화 , 어플 이용자와 동네정보로 동네친구 찾기 서비스 그리고 전력회사와 전력소비자로 전력공급 네트워크도 구성할 수 있다. 

 

고로, 이분 그래프는 같은 집합에 있는 노드 사이에 간선이 있으면 안 된다.  지훈이의 취미가 축구인데, 축구를 하는 사람이 농구이면 안 된다. 지훈이의 취미는 축구인데, 축구가 취미인 사람이 철민이어야 한다. 그렇다면 지훈이와 철민이는 축구로 매칭된다고 할 수 있다. 

 

 

이분 그래프 확인법

 

그래프가 주어졌을 때, 이분 그래프임을 확인하려면 간선으로 연결된 노드가 서로 다른 집합의 노드여야 한다. 노드에 색을 칠하여 인접노드가 다른 색상인지 탐색하는 방법으로 이분 그래프를 확인한다. 탐색하는 방법에는 DFS, BFS가 있다. 

 

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

1707번: 이분 그래프

 

대표적인 이분 그래프를 확인하는 문제이다. 위 문제를 BFS로 풀어보았다.

 

코드

#BOJ1707 이분그래프
from collections import deque
import sys
input = sys.stdin.readline

k = int(input())
R,B = 1,-1 # 서로 다른 집합의 색상정보 ( R : RED, B : BLUE )

#넓이 우선 탐색 ( BFS )
def bfs(bipartite,i) :
  global flag 
  bipartite[i] = R # RED로 칠하기 
  q =deque([i])
  while q :
    i = q.popleft() #탐색노드 가져오기
    for node in graph[i] : # 인접노드 가져오기 
      if bipartite[node] != 0 : #방문된 노드라면 색상비교하기
        if bipartite[node] == bipartite[i] : #색상이 일치하면 이분 그래프X
          flag = False
          return #함수종료
      else : #방문된적 없다면 반대 색상으로 색칠하기
        bipartite[node] = -bipartite[i] 
        q.append(node) # 큐에 넣기 

#그래프 탐색시작 
for _ in range(k) :
  v,e = map(int,input().split())  # 간선정보 가져오기
  bipartite = [0] * (v+1) # 색상 테이블 
  graph = [[] for _ in range(v+1)] # 그래프

  #그래프 초기화
  for i in range(e) :
    a,b = map(int,input().split())
    graph[a].append(b) # 양방향 그래프
    graph[b].append(a)

  #BFS로 이분그래프 색칠하기
  flag = True
  for i in range(1,v+1) :
    if not flag : break
    if bipartite[i] == 0 : bfs(bipartite,i)

  #출력
  print("YES" if flag else "NO")