[Algorithm][Python3][BOJ 1707번] 이분 그래프

 

문제

 

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

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

 

풀이

 

풀이 - BFS와 DFS

 

이분 그래프는 쉽게 말하자면 그래프에서 연결되어 있는 노드끼리 같은 색깔을 칠했을 때 총 두가지 색깔이 나온다는 의미다.

모든 노드를 탐색하면서 색깔을 칠하는 방식으로 해결했고 이 때 DFS를 이용했다. (BFS로도 풀 수 있다고 한다.)

재귀로 풀면서 해결하는데 문제는 비연결 그래프인 걸 감안하고 풀어야 한다.(이거 때문에 계속 오류남..)

 

탐색을 하면서 인접한 노드에 dfs를 수행한다. 이 때 만약 색이 같거나, 혹은 이미 방문했으면서 나와 인접한 노드가 색이 같다면 이분 그래프가 아닌 것으로 판단했다.

 

Python 코드

 

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**6)

def dfs(v, color) :
    visited[v] = color
    for i in graph[v] : # v와 인접한 정점 방문
        if visited[i] == 0 : # 방문하지 않았을 때
            if not dfs(i, -color) : # 다른 컬러로 dfs -> False -> False 반환
                return False
        elif visited[i] == visited[v] : # 이미 방문한 인접한 정점인데 color가 같으면
            return False
    return True
  
K = int(input())

for _ in range(K) :
  V, E = map(int, input().split(' '))
  graph = {x : [] for x in range(1, V+1)} # 빈 그래프 생성
  visited = [0] * (V + 1) # 방문한 정점
  for _ in range(E) :
    [a, b] =map(int, input().split(' '))
    graph[a].append(b)
    graph[b].append(a)

  isBipartiteGraph = True
  
  for i in range(1, V+1) :
      if visited[i] == 0 :
          isBipartiteGraph = dfs(i, 1)
          
          if not isBipartiteGraph :
              break

  if isBipartiteGraph :
    print('YES')
  else :
    print('NO')

 

 

후기 및 보완할 점

 

해결방법을 생각해내는 건 할 수 있었는데 구현과 예외(비연결 그래프)를 생각해내는 거에서 시간이 걸렸다.

BFS로도 한 번 풀어볼 만 한 문제인 것 같다.