[Python 3] BOJ - 1707 "이분 그래프"

 # 문제 링크 : https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

 # 풀이 :

개인적으로 문제의 핵심은 BFS/DFS라고 생각한다. 조금 더 구체적으로는 정점을 방문했는지 체크하는 배열의 응용이라고 생각한다. 이분 그래프란 어떤 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프이다.

<그림 1. 이분 그래프의 예시>

 그림 1에서 세 그래프 모두 이분 그래프이다. 세 그래프 모두 (1,2) / (3,4)의 집합으로 나눌 수 있다. 그런데 두번째 그래프를 보면 반드시 모든 정점이 간선을 가지는 것은 아니며 세번째 그래프를 보면 반드시 두 정점 사이에 경로가 존재하지 않을 수도 있지만 이분 그래프를 만족시킬 수 있다.

<그림 2. 이분그래프가 아닌 예시>

 그림 2에서는 그림 1의 이분 그래프가 어떤 간선 하나에 의해서 이분 그래프의 조건을 만족하지 않는 경우를 나타낸 것이다. 첫번째와 두번째 그래프를 보면 사이클의 존재 유무가 이분 그래프를 결정하는 것 같이 보이지만 반례로 세번째 그래프가 있다.

 가장 단순하게 이분 그래프인지 아닌지를 구하는 방법은 모든 조합을 다 구하는 것이지만 이는 절대로 시간안에 정답을 구할 수 없다. 그런데 BFS/DFS를 이용하면 시간안에 정답을 구할 수 있다. 왜냐하면 BFS/DFS는 그래프의 정점을 한번씩만 지나기 때문이다. 일반적인 BFS/DFS의 경우 지금 방문하려는 정점이 이전에 방문이 되었는지를 조사하는 배열이 필수적이다. 왜냐하면 그런 장치가 없다면 모든 정점을 한번씩만 지날수가 없기 때문이다. 그런데 방문함과 동시에 그 정점에 대한 번호를 부여한다면, 그리고 그 번호가 무한정 많은 것이 아니라 이분 그래프이기에 단 두개의 수만 허용된다면 우리는 모든 정점에 대해 2개의 수로 구분할 수 있을 것이다.

<그림 3. group num을 적용한 그래프>

 그림 3은 현재 그래프에서 시작 정점을 2번 정점으로 한 결과이다. 2와 인접한 정점 1, 3, 4가 아직 방문하지 않았으므로 1부터 먼저 방문한다. 인접한 정점이므로 1,3,4의 그룹 번호는 2의 그룹 번호와 달라야 하므로 지금 방문하는 정점 1의 그룹 번호는 2가 된다.

 2와 인접한 정점 중 아직 방문하지 않은 정점은 3, 4이다. 역시 3의 그룹 번호는 2가 된다. 현재 정점이 3이고 3과 인접한 정점 중 4는 아직 방문하지 않았으므로 4는 3과 그룹 번호가 달라야 한다. 따라서 4의 그룹 번호는 1이 된다. 이제 방문하지 않은 정점이 없으므로 탐색은 종료된다. 

 현재 그래프는 1과 2의 그룹번호로 두 집단으로 나뉘어졌다. 그런데 그룹번호로 나뉘어 진다고 하여 반드시 그 그래프가 이분 그래프라는 보장이 없다. 그룹번호로 나뉘어지면서 같은 그룹내에서는 간선이 존재하지 않는 그래프가 이분 그래프이므로, 탐색 시 현재 정점과 인접한 정점 중 아직 방문하지 않은 정점이 있다면 현재 정점과 다른 그룹 번호를 부여하고 이미 방문했던 정점이라면 경우를 두가지로 나눈다. 

 현재 정점과 인접하면서 이미 방문했으나 그룹 번호가 다른 정점이라면 이분 그래프의 조건을 만족하기 때문에 BFS라면 큐에 넣을 필요가 없고, DFS라면 함수를 재귀호출하지 않아도 된다. 반대로 현재 정점과 인접하면서 이미 방문했으나 그룹 번호가 같다면 이분 그래프의 조건을 만족하지 않는다. 이 때 주의할 점은 반드시 1번 정점이 연결되어 있지 않다는 점이다. 따라서 한번도 방문하지 않은 정점이 있을 때 마다 BFS/DFS를 호출해야 한다

 

 # 코드

import sys, collections

# 테스트 케이스 수 입력
k = int(sys.stdin.readline())
for _ in range(k):
    # 정점, 간선 입력부
    v, e = map(int, sys.stdin.readline().split())
    
    # adj : 인접 리스트
    adj = [[] for _ in range(v + 1)]
    
    # label : 방문하지 않았다면 -1인 방문 확인 배열
    label = [-1] * (v + 1)
    
    # 그래프 입력부
    for i in range(e):
        a, b = map(int, sys.stdin.readline().split())
        adj[a].append(b)
        adj[b].append(a)
    q = collections.deque()
    ans = True
    for i in range(1, v + 1):
        # ans가 False인 경우 탈출
        if not ans:
            break
            
        # 아직 방문하지 않은 정점이 있다면 bfs실행
        if label[i] == -1:
            q.append(i)
            label[i] = 1
            while q:
                # bfs 도중 이분 그래프가 아니라면 bfs 탈출
                if not ans:
                    break
                now = q.popleft()
                for next in adj[now]:
                    # next, 즉 방문할 정점이 방문하지 않았다면 그룹 번호를 바꿔 방문
                    if label[next] == -1:
                        label[next] = (label[now] + 1) % 3
                        q.append(next)
                    else:
                        # next가 방문했으나 그룹 번호가 같다면 이분 그래프가 아니므로 ans 갱신
                        if label[next] == label[now]:
                            ans = False
    
    # 정답 출력
    if ans:
        print('YES')
    else:
        print('NO')