[백준/1707] 이분 그래프 (Python)

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

1707번: 이분 그래프

 

Difficulty : Gold 4

 

Status : Solved

 

Time : 00:11:01

 

---

 

문제 설명

 

 

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다. 

 

출력

 

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

 

입력 예시

 

2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2

 

출력 예시

 

YES
NO

 

 

---

 

풀이

 

이분 그래프의 개념을 처음 알게 되었다.

 

https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84

이분 그래프 - 위키백과, 우리 모두의 백과사전

 

각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할하려면, 어떤 정점에서 인접한 다른 정점은 모두 다른 집합에 포함되어야 한다. 또한, 그 다른 집합에 속한 모든 정점들 역시 인접 정점은 다른 집합(그리고 초기의 그 정점과 동일한 집합)에 포함되어 있어야 한다.

 

따라서 이분 그래프가 성립하려면, 어떤 지점에서 다른 지점까지의 거리(거쳐야 하는 간선 수)가 모두 홀수거나, 모두 짝수여야 한다. 만약 홀수라면 다른 집합, 짝수라면 같은 집합이다. 이 전제 하에서 홀수 거리와 짝수 거리가 동시에 존재한다면 이분 그래프의 정의를 충족하지 않는다고 볼 수 있다.

 

즉 탐색하지 않은 모든 노드를 시작점으로 하여 BFS 혹은 DFS로 탐색을 수행하면 된다. visited 배열은 그 노드에 도달하였을 때의 거리가 홀수인지, 짝수인지 둘을 저장하면 된다. 모든 노드에 대한 탐색이 끝나고, 이 홀수 거리와 짝수 거리의 존재를 검사하도록 한다. 이로써 이분 그래프 여부를 판별할 수 있겠다.

 

풀이 코드

import sys
input = sys.stdin.readline

def solve() :
  v, e = map(int, input().split())

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

  visited = [[0]*2 for _ in range(v)]

  def dfs(i) :
    q = [ (i, 0) ]
    visited[i][0] = 1
  
    while q :
      node, odd = q.pop()
      for nxt in edge_list[node] :
        if not visited[nxt][1-odd] :
          visited[nxt][1-odd] = 1
          q.append((nxt, 1-odd))

  for i in range(v) :
    if sum(visited[i]) == 0 :
      dfs(i)
  
  for i in range(v) :
    if sum(visited[i]) == 2 :
      print("NO")
      return
  print("YES")
  return

for _ in range(int(input())) :
  solve()

풀이 완료!