이분 그래프 [백준 1707] - python

from collections import deque
import sys 

def BOJ1797() :
  def bfs(start) :
    bi[start] = 1
    queue = deque()
    queue.append(start)
    while queue :
      curr = queue.popleft()
      for i in graph[curr] :
        if bi[i] == 0 :
          bi[i] = -bi[curr]
          queue.append(i)
        else :
          if bi[i] == bi[curr] :
            return False
    return True

  k = int(sys.stdin.readline())
  for _ in range(k) :
    global graph
    global flag
    global bi
    global queue

    flag = "YES"
    V, E = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(V+1)]
    bi = [0 for _ in range(V+1)]
    for _ in range(E) :
      u, v = map(int, sys.stdin.readline().split())
      graph[u].append(v)
      graph[v].append(u)

    for k in range(1, V+1) :
      if bi[k] == 0 :
        if not bfs(k) :
          flag = "NO"
          break
        
    print(flag)

BOJ1797()

 

접근방법 :

1. 주어진 그래프에서 정점을 이분할 할수 있을까에 대한 문제이다. 

(아래 이미지는 이분 그래프가 된다. 인접한 친구들은 다른 색으로 칠해주면 된다)

2. bi는 이분그래프의 색깔에 대한 배열이다. 선언시에 0으로 초기화 해준다.

3. 앞으로 칠해주는 색은 동일하게 한뒤 그래프 탐색을 통해 인접한 노드들에 대한 색깔은 현재 칠하는 색과 반대로 칠한다.

4. 탐색을 계속 진행하면서 나와 이미 색깔이 칠해져있고 그 색깔이 나와 같은 색이라면 이분그래프의 조건에 성립하지 않게 된다.

5. 어려운 문제였다....

 

 

장애물 이였던 것 :

1. 문제 이해 자체가 어려웠었고 다른 분들의 풀이를 참고 하였습니다.

 

 

 

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

1707번: 이분 그래프

https://pacific-ocean.tistory.com/349

[백준] 1707번(python 파이썬)