[BOJ] 1707 이분 그래프

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

그래프의 노드에 2가지 색칠하는데 인접한 노드끼리 서로 다르게 색칠할 수 있는지 묻는 문제이다.

dfs로 돌면서 색칠하고, 만약 방문했다면 현재 노드와 방문하려고 했던 노드의 색이 같은지 다른지에 따라 결과가 나오게 했다.

코드 1 - 시간초과

from collections import defaultdict

def dfs(start, color, graph, visited, chk):
  
  for next in graph[start]:
    if visited[next] == -1:
      visited[next] = abs(color-1)
      chk = dfs(next, abs(color-1), graph, visited, chk)
      visited[next] = -1
    elif visited[next] == visited[start]:
      chk = False
      
  return chk

for _ in range(int(input())):
  v, e = map(int, input().split())
  graph = defaultdict(list)
  
  for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
  visited = [-1 for _ in range(v+1)]
  
  visited[1] = 0
  print("YES" if dfs(1, 0, graph, visited, True) else "NO")

dfs로 했는데 시간초과가 났다.

코드 2 - 시간초과

from collections import defaultdict

for _ in range(int(input())):
  v, e = map(int, input().split())
  graph = defaultdict(list)
  
  for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
  visited = [-1 for _ in range(v+1)]
  
  visited[1] = 0
  que = [(1, 0)]
  idx = 0
  chk = True
  while idx < len(que):
    if not chk:
      break
    now, color = que[idx]
    idx += 1
    
    for next in graph[now]:
      if visited[next] == -1:
        que.append((next, abs(color-1)))
        visited[next] = abs(color-1)
      elif visited[next] == visited[now]:
        chk = False
        break
  
  print("YES" if chk else "NO")
  

BFS로 바꿔봤는데, 재귀도 안 쓴 코드인데도 시간초과가 발생했다. 왜지 도대체라고 생각했는데 연결되지 않은 그래프가 있는 경우를 고려하지도 못했고, input도 겁나 커서 그런 것 같았다.

코드 3 - DFS

from collections import defaultdict
import sys

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

def dfs(start, color, graph, visited):
  visited[start] = color
  for next in graph[start]:
    if visited[next] == -1:
      if not dfs(next, 1 - color, graph, visited):
        return False
    elif visited[next] == color:
      return False
  return True

for _ in range(int(input())):
  v, e = map(int, input().split())
  graph = defaultdict(list)
  
  for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
  visited = [-1 for _ in range(v+1)]
  
  answer = True
  
  for i in range(1, v+1):
    if visited[i] == -1:
      if not dfs(i, 0, graph, visited):
        answer = False
  
  print("YES" if answer else "NO")

초기화 절차를 조금 수정하고, visited를 참고해서 모든 점에 대해서 방문하지 않았다면 검사하도록 했다. 그리고 readline으로 입력 속도를 늘리고 recursion 제한을 풀어주었다.

코드 4 - BFS

from collections import defaultdict
import sys

input = sys.stdin.readline

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

  chk = True
  for i in range(1, v+1):
    if visited[i] == -1 and chk:
      visited[i] = 0
      que = [(i, 0)]
      idx = 0

      while idx < len(que) and chk:
        now, color = que[idx]
        idx += 1
        
        for next in graph[now]:
          if visited[next] == -1:
            que.append((next, abs(color-1)))
            visited[next] = abs(color-1)
          elif visited[next] == visited[now]:
            chk = False
            break
  
  print("YES" if chk else "NO")
  

BFS에서는 readline으로 입려제한을 풀어주었다.
그리고 chk의 위치를 조정하고 마찬가지로 모든 점에 대해서 방문여부를 확인하고 BFS 절차를 시작되도록 했다.