Baekjoon Online Judge 1707번 파이썬

문제 링크
https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

이분 그래프: 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두가지 색으로만 칠할 수 있는 그래프.
모든 노드로 DFS 해보아야함.
DFS 함수에서 마지막에 ‘이미 방문했던 노드는 방문하지 않는다.’에 그 두개의 노드가 같은 집합(색)인지 판단하는 코드를  추가해야함.
이분 그래프가 아니면 더이상 탐색하지 않아야함.

이분 그래프를 몰라서 유튜브 영상과 블로그 글을 보고 이해했다.
그래도 코드를 작성하기 너무 어려웠다. 여러번 풀어 볼 필요가 있다.


중간에 실수로 sys.stdin.readline() 대신에 input()을 넣어놔서 자꾸 시간초과가 떴다…

정답 코드

import sys
sys.setrecursionlimit(10 ** 6)

def dfs(start, group):
  check[start] = group
  for i in graph[start]:
    if not check[i]:
      connected_node = dfs(i, -group) #방문하지 않았다면, 그룹값 -1로 dfs를 한다.
      if not connected_node: #만약 아래 elif로 인해 False가 나왔다면 False를 리턴한다. 
        return False
    elif check[i] == check[start]: #이웃한 방문한 곳인데 그룹이 같으면 False
      return False
  return True #나머지는 True

K = int(sys.stdin.readline())

for i in range(K):
  V, E = map(int,sys.stdin.readline().split())
  check = [False] * (V+1)
  graph = [[] for i in range(V+1)]
  for i in range(E):
    from_n, to_n = map(int, sys.stdin.readline().split())
    graph[from_n].append(to_n)
    graph[to_n].append(from_n)

  for i in range(1, V + 1):
    if not check[i]:  # 정점을 방문하지 않았다면 그 정점을 시작점으로 dfs 수행
      result = dfs(i, 1)
      if not result:  # 만약 result가 False가 나왔다면 더이상 수행할 
        break  
  print("YES" if result else "NO")