[백준BOJ] 1707번 이분그래프.py

 

백준 저지에서 1707번 이분 그래프를 파이썬을 통해 풀어 보았다. 

 

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

1707번: 이분 그래프

 

 

1707번 이분 그래프.py

tomy9729/Algorithm

 

 

1707번 이분 그래프

문제
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.
그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

문제에 앞서 이분 그래프가 뭔지 정확히 이해해야 한다. 이분 그래프란 어떤 그래프에 대해서 인접한 노드끼리 서로 다른 색을 로만 칠할 때 모든 노드를 두 가지 색으로만 칠할 수 있는 그래프를 말한다. 

이분 그래프는 BFS나 DFS로 확인할 수 있으며 나는 BFS로 풀었다. 확인하는 방법은 다음과 같다.

1. BFS로 탐색하면서 정점 방문 시 한 가지 색으로 칠한다.
2. 현재 노드에서 인접한 노드로 방문할 때 방문하지 않은 노드라면 현재 노드와 다른 색으로 칠한다.
3. 현재 노드에서 인접한 노드로 방문할 때 방문한 노드라면 현재 노드와 다른 색인지 확인한다.
4. 만약 현재 노드와 인접한 노드가 같은 색이라면 이분 그래프가 아니다.
5. 위 과정을 끝까지 완료했다면 이분 그래프이다.

BFS로 탐색하되 위 과정을 탐색하는 과정에서 구현하면 된다. 코드는 다음과 같다.

#1707번 이분 그래프
#import sys
#input = sys.stdin.readline #입력 속도 상향
from collections import deque # 큐 성능 상향
def BFS(graph,visit,start) : 
  visit[start] = 1 #색은 1과 -1이 있으며 0이면 아직 방문하지 않은 노드
  q = deque()
  q.append(start)
  while q : 
    now = q.popleft()
    color = visit[now]
    for i in graph[now] : #현재 노드로부터 인접한 노드에 대해서
      if visit[i] == 0 :  # 방문하지 않은 노드라면
        q.append(i)   # 큐에 삽입
        visit[i] = -1*color # now와 다른 색으로 칠함
      elif visit[now] == visit[i] : #방문한 노드이고, now와 색이 같다면
        return False  # False 반환
  return True
if __name__ == "__main__":
  t = int(input())
  for i in range(t) : 
    v,e = map(int, input().split())
    visit = [0]*(v+1)
    graph = [[] for i in range(v+1)]
    
    for j in range(e) : 
      p1, p2 = map(int, input().split())
      graph[p1].append(p2)
      graph[p2].append(p1)
    
    result1 = BFS(graph,visit,1)

    visit = [0]*(v+1)
    result2 = BFS(graph,visit,p2)
    if result1 and result2 : 
      print("YES")
    else : 
      print("NO")