[백준1707&파이썬] BFS를 활용하여 이분 그래프를 판별하는 방법

# 문제

1707번: 이분 그래프

# 코드

import sys
from collections import defaultdict
from collections import deque

RED = 1
BLUE = -1

def solve():
  V, E = map(int, sys.stdin.readline().split())  # V 정점의 개수, E 간선의 개수
  graph = defaultdict(list)
  visit = [0] * (V + 1)  # 0 == 방문X , 1 == RED , -1 == BLUE
  for _ in range(E):
    a, b = map(int, sys.stdin.readline().split())
    # 양방향 연결
    graph[a].append(b)
    graph[b].append(a)

  # BFS를 이용해서 확인함.
  for i in range(1, V + 1):
    if visit[i] == 0:  # 방문하지 않은 그래프라면
      dq = deque()
      dq.append( (i, RED) )
      visit[i] = RED

      while len(dq) != 0:
        cur = dq.popleft()  # ( VERTEX, COLOR )
        # print(cur)
        for neighbor in graph[cur[0]]:  # 인접한 이웃 노드들
          ## 다음 색칠될 색을 미리 확정해주기
          if cur[1] == RED:
            color = BLUE
          else:
            color = RED
          next = (neighbor, color)
          ## --- ##

          if visit[neighbor] == 0:  # 해당 이웃을 방문하지 않았다면
            dq.append(next) # 큐에 추가
            visit[next[0]] = next[1] # 색칠하기
            # print("here")


          else : # 방문 했었다면, 이웃 노드의 색은 next색이어야함
            if visit[neighbor] != next[1] :
              print("NO")
              return
  print("YES")
  return


K = int(sys.stdin.readline())
for _ in range(K):
  solve()

 

# 풀이

• 인접리스트와 인접행렬에 대해서 고민해봤고, Vertex가 최대 20,000개이기 때문에 낭비되는 메모리를 없애기 위해서 defaultdict을 이용한 인접리스트방법을 사용했다. 
• 이분그래프가 뭔지에 대한 이해가 먼저 필요하다. 문제에 주어진 보기를 읽고도 이분 그래프가 이해가 되지 검색해서 알아 봤다. 

(1), (2), (3)

• 위와 같이, 같은 노드끼리는 인접하지 않으면 된다.

• 고민했던 것 중 하나가, 시작노드가 무작위로 선택될때, 시작 색깔에 따른 영향이 있지 않을까 싶었다. 그래서 (1) 순서만 다르게 색을 칠해봤다.위와 같이 여전히 이분 그래프가 유지됨을 알 수 있었다. 
• 핵심 풀이는, BFS는 하나의 Tick 단위로 넓이 우선탐색을 진행한다. 즉 현재 Tick에 속한 노드와 다음 Tick에 속한 노드의 색을 다르게 해줘야 한다. 그렇게 하기 위해서, 방문처리를 확인하고 방문이 아니라면 방문 후 연결된 노드의 색을 칠해준다. 이 때 현재와 다른 색으로 칠해준다. 만약 이웃한 노드가 이미 방문처리가 돼 있다면, 현재의 색깔과 다른지 확인한다.