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

• Problem Link : https://www.acmicpc.net/problem/1707

문제

• 그래프가 입력으로 주어졌을 떄, 이 그래프가 이분 그래프인지 아닌지 판별

입력

• 첫째 줄, 테스트 케이스 K
• 각 테스트 케이스의 첫째 줄, 그래프 정점의 수 V와 간선의 개수 E
• 테스트 케이스의 둘째 줄부터 E개의 줄, 인접한 두 정점의 번호 u, v

출력

• 테스트 케이스 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력

이분 그래프

집합이 두 개 있을 때, 인접한 노드끼리 서로 다른 집합에 위치할 수 있다면 이분 그래프

위와 같이 모든 노드가 인접한 노드와 다른 집합이어야 한다.

풀이

DFS 방식으로 모든 노드를 방문한다. 이 때 방문할 때 마다 노드에게 그룹을 부여한다.

• 여기서 노드에 색을 부여해서 이분 그래프인지를 판단한 것처럼 그룹을 1, -1로 구분지어 노드에게 부여하고 만약 인접한 노드가 같은 그룹이면 이분 그래프가 아니다.

• 따라서 다음과 같이 해결할 수 있다.

  	1. DFS 방식으로 방문하지 않은 노드들을 방문한다.
  	2. 이미 방문한 노드와 인접하다면 인접한 해당 노드와 자신에게 주어진 bit를 비교한다.
  	3. bit가 같다면 이 그래프는 이분 그래프가 아니므로 return시키다.
  	4. bit가 다르다면 다시 모든 노드를 방문할 때까지 DFS를 진행한다.
  	5. 모든 노드 방문이 끝났을때 이분 그래프라고 판단되면 YES, 아니면 NO를 출력한다.

• DFS 부분을 아래 코드와 같이 구현하였다.
  

DFS

def dfs(graph, v, group):
    visited[v] = group
    for i in graph[v]:
        if not visited[i]:
            flag = dfs(graph, i, -group)
            if not flag:
                return False
        elif visited[i] == visited[v]:
            return False
    return True

오류 및 해결

이분 그래프는 짝수 개의 정점, 홀수 개의 간선으로 구성된 홀수 길이의 순환이 생기게 되면 반드시 이분 그래프가 아니며 홀수 길이의 순환이 없으면 반드시 이분 그래프이다.

따라서 이렇게 다른 집합인지 아닌지 계속 확인하는 방식이 아니어도 이미 방문한 노드를 방문하게 될 경우 순환이 있다는 것을 의미하고 해당 순화의 길이가 홀수인지 짝수인지를 확인해 이분 그래프 여부를 파악하는 방법도 있다.

추가적으로 BFS 방식을 이용해서도 해당 프로그램을 구현할 수 있다.

코드

• DFS & BFS

import sys

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


def dfs(graph, v, group):
    visited[v] = group
    for i in graph[v]:
        if not visited[i]:
            flag = dfs(graph, i, -group)
            if not flag:
                return False
        elif visited[i] == visited[v]:
            return False
    return True


from collections import deque


def bfs(graph, v, group):
    queue = deque([v])
    visited[v] = group
    while queue:
        n = queue.popleft()

        for i in graph[n]:
            if not visited[i]:
                queue.append(i)
                visited[i] = -1 * visited[n]
            elif visited[i] == visited[n]:
                return False
    return True


K = int(input())
for _ in range(K):
    V, E = map(int, input().split())
    graph = [[] for _ in range(V + 1)]
    visited = [False] * (V + 1)

    for i in range(E):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    for i in range(1, V + 1):
        if not visited[i]:
            result = bfs(graph, i, 1)
            if not result:
                break

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