[Python] 백준 - 1707 이분 그래프

백준 - 1707 이분 그래프

문제

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

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

입력

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

출력

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

제한

• 2 ≤ K ≤ 5
• 1 ≤ V ≤ 20,000
• 1 ≤ E ≤ 200,000

 

문제해결방법

 

<이분 그래프 (Bipartite Graph)>

 

1. 위 그림과 같은 그래프가 이분그래프이다. 연결된 그래프의 노드에 색깔을 칠했을 때 번갈아 색깔이 등장하면 되는 개념이다.

2. dfs나 bfs로 그래프를 탐색하고 연결하되 방문리스트를 2개로 구분해 저장하고 다음 노드를 방문할 때 색깔이 겹치는지 여부를 판단하는 코드가 있으면 된다. (그래프가 끊어져서 2개 이상 있을 수도 있으므로 이를 고려한다.)

3. dfs에서 return이 있고, 재귀함수 호출 부분을 저장하면 끝까지 파고들어간 후 연쇄적으로 결과를 저장하거나 판정할 수 있다.

 

- 코드

1. dfs

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

def dfs(idx, chk):
    v[idx] = chk
    for next in graph[idx]:
        if v[next] == 0:
            res = dfs(next, -chk)
            if not res:
                return False
        elif v[idx] == v[next]:
            return False
    return True

for _ in range(int(input())):
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    v = [0 for _ in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    for i in range(1, n+1):
        if v[i] == 0:
            res = dfs(i, 1)
            if not res:
                print("NO")
                break
    else:
        print("YES")

 

2. bfs

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def bfs(idx, chk):
    q = deque()
    q.append(idx)
    v[idx] = chk
    while q:
        idx = q.popleft()
        for next in graph[idx]:
            if v[next] == 0:
                v[next] = -v[idx]
                q.append(next)
            elif v[next] == v[idx]:
                return False
    return True

for _ in range(int(input())):
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    v = [0 for _ in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    for i in range(1, n+1):
        if v[i] == 0:
            res = bfs(i, 1)
            if not res:
                print("NO")
                break
    else:
        print("YES")