백준 1707 - 파이썬

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

1707번: 이분 그래프

이분 그래프는 인접한 노드끼리 서로 다른 집합에 넣을 수 있다면 이분 그래프이다.

아래의 경우는 서로 다른 집합에 속하므로 이분 그래프가 아니다.

출처: 위와 동일

이분 그래프는 처음 접해보는 개념이기도 하고, 풀이 방법도 떠오르는게 없어 구글링을 해봤다. 각 코드의 출처는 제목에 연결해 두겠다.

BFS 1

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

def bfs(start,group):
  q = deque([start])
  visited[start] = group

  while q:
    x = q.popleft()
    for i in graph[x]:
      if not visited[i]:
        q.append(i)
        # 그룹을 1과 -1으로 나누며, 인접 노드는 -1을 곱하여 그룹 구분
        visited[i] = visited[x] * -1 
        # 현재 노드와 인접 노드의 그룹이 같다면 이분 그래프가 아님
      elif visited[i] == visited[x]:
        return False

  return True

for _ in range(int(input())):
  v,e = map(int,input().split())
  graph = [[] for i in range(v+1)]
  visited = [False] * (v+1)

  for _ in range(e):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

  for i in range(1,v+1):
    if not visited[i]:
      result = bfs(i,1)
      if not result:
        break

  print("YES" if result else "NO")

BFS 2

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

k = int(input())

def bfs(graph,start):
  q = deque()
  q.append(start)
  if visited[start] == 0:
    visited[start] = 1
  while q:
    v = q.popleft()
    color = visited[v]

    for i in graph[v]:
      if visited[i] == 0:
        q.append(i)
        if color == 1:
          visited[i] = 2
        else:
          visited[i] = 1
      elif visited[i] == 1:
        if color == 1:
          print("NO")
          return False

      elif visited[i] == 2:
        if color == 2:
          print("NO")
          return False

  return True


for i in range(k):
  flag = 0
  v,e = map(int, input().split())
  graph = [[] for _ in range(v+1)]
  visited = [0] * (v+1)
  for j in range(e):
    a,b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

  for k in range(1, v+1):
    if not bfs(graph,k):
      flag = 1
      break
  if flag == 0:
    print("YES")

DFS

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

k = int(input())

def dfs(start,visited,graph,group):
  visited[start] = group

  for v in graph[start]:
    if visited[v] == 0:
      result = dfs(v, visited, graph, -group)

      if not result:
        return False

    else:
      if visited[v] == group:
        return False

  return True

for _ in range(k):
  v,e = map(int, input().split())
  graph = [[] for _ in range(v+1)]
  visited = [0] * (v+1)
  for _ in range(e):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

  for i in range(1, v+1):
    if visited[i] == 0:
      result = (dfs(i, visited, graph, 1))
      if not result:
        break

  print("YES") if result else print("NO")

DFS로 푼 문제도 group을 -1과 1로 나눠 구분하는 방식은 똑같다. 

 

느낀점

처음에 문제를 읽고 어떻게 풀어야 하나 막막했는데 다른 사람들이 정리해 둔 개념과 코드를 천천히 읽어보니 개념도 이해됐고, 코드도 이해되었다. 이분 그래프의 아주 기본적인 문제인거 같으니 머릿속에 잘 기억해 둬야 되겠다.