[백준 1707번] 이분 그래프 파이썬 풀이

이분 그래프 

2 초

256 MB

93062

25289

15511

24.246%

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (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

예제 입력 1

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

예제 출력 1

YES
NO

 

이 문제를 해결하기 위해선 먼저 이분그래프가 무엇인지부터 알아야한다.

 

이분 그래프란 인접한 정점을 서로 다른 색으로 칠할때 단 2가지 색만을 사용할 수 있는 그래프다.

이 말이 무슨 뜻인지 문제의 예제를 직접 그림으로 그리면서 설명해보겠다.

 

첫번째 예제의 경우 1-3, 3-2 노드가 붙어 있으므로 왼쪽과 같은 그림이 그려지며, 인접한 정점을 빨강,파랑 2가지 색상만을 사용하여 칠할 수 있다. 따라서 이분 그래프이다.

 

 

두번째 예제의 경우를 한번 살펴보자. 먼저 1번 노드를 빨강색으로 칠하고 인접한 3번 노드를 파랑색으로 칠하였다. 이후 3과 인접한 노드인 4번,2번 노드를 둘 다 빨강색으로 칠하였다. 여기서 문제가 발생한다. 4번노드와 2번 노드는 인접한 노드지만 서로 같은 색상이 칠해졌기 때문에 이분 그래프가 될 수 없다.

 

그래프가 이분 그래프인지 아닌지 확인하는 가장 간단한 방법은 그래프 탐색을 이용하는 것이다.

임의의 정점에서 깊이우선탐색을 시작하여 현재 정점과 인접한 정점이 아직 방문하지 않은 정점인 경우 이전 정점과 다른 색상으로 칠하고, 이미 방문한 정점이라면 현재 자신의 색상과 비교하여 같은 색상인지 확인한다. 

이 과정에서 같은 색상이 이미 칠해져있다면 인접한 정점이 서로 같은 색상으로 칠해진다는 의미이므로 이분그래프가 될 수 없고 깊이우선탐색을 문제없이 끝까지 마쳤다면 해당 그래프는 이분 그래프가 된다.

 

이 문제에서 주의해야 할 점은 그래프의 모든 정점이 항상 모두 연결되어있지 않다는 점이다.

 

단편적인 예시로 아래와 같은 형태도 그래프이며 '단절 그래프'라고 부르는데, 단절 그래프에 포함된 그래프 집합을 모두 확인해서 모든 정점이 2가지 색상으로 칠해져야 이분그래프라고 부를 수 있기 때문에 방문하지 않은 모든 정점에 대하여 탐색을 수행해야 한다.

 

이 아이디어를 코드로 옮기면 아래와 같다.

from collections import deque
'''
이분 그래프 => 인접한 정점을 서로 다른 색으로 칠할 수 있는 그래프

<이분 그래프>          <이분 그래프x>
1(R) -  3(B)        1(R) - 2(B)
        |                /   |
        2(R)        3(R) - 4(R)
        
두번재 예시의 경우 4는 인접한 정점 3과 같은 색으로 칠해지므로 이분 그래프가 될 수 없다.
'''
def isBinaryGraph(start):
    queue = deque([start])
    visited[start] = 1 # 1번 노드는 색상코드 1로 기입
    while queue:
        node = queue.popleft()
        # 인접 노드에 대해서 탐색 수행
        for iNode in graph[node]:
            # 인접 노드 중에 방문했던 적이 있는 노드가 존재한다면 현재 자신의 색과 같은지 비교
            if visited[iNode] != 0:
                if visited[iNode] == visited[node]:
                    # 현재 자신의 색과 같다 -> 인접 노드가 같은 색으로 칠해졌다 -> 이분그래프 불가능
                    return False
            else: # 방문한 적이 없는 노드에 대해
                visited[iNode] = -(visited[node]) # 현재 색과 다른 색상으로 기록
                queue.append(iNode)
    return True # 문제없이 끝까지 수행하였다면 이분그래프가 가능함

for _ in range(int(input())):
    v,e = map(int,input().split())
    visited = [0]*(v+1) # 0방문한적 없는 노드, 1,-1은 색상
    graph = [[] for _ in range(v+1)]
    for _ in range(e):
        a,b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
        
    # 그래프가 모두 연결되어있지 않을 수 있음..?
    isBinary = True
    for v in range(1, v+1):
        if visited[v] == 0:  # 방문하지 않은 노드에서 BFS 시작
            if not isBinaryGraph(v):
                isBinary = False
                break

    print("YES" if isBinary else "NO")