[백준] 1707번 - 이분 그래프 (DFS, BFS) - 결과 포함

www.acmicpc.net/problem/1707

1707번: 이분 그래프

그래프의 종류 중 하나인 이분 그래프를 판별하는 문제이다.

이분 그래프는 한 정점으로부터 이동한 정점들 사이에서 BFS가 또 수행되면 성립하지 않는다.

즉, 한 정점에서 이미 방문한 정점에 대해 방문했을 때 그 정점이 같은 정점으로부터 방문 받은 정점이라면 이분 그래프가 아닌 것이다.

이를 체크하기 위해서 한 정점으로부터 이동할 때마다 방문을 체크하는 visited 리스트에 두 가지의 숫자를 넣어서 구분했다.

 

만약 다음에 방문하고자 하는 정점이 방문을 하지 않은 정점이라면 큐에 정점을 추가한다.

그리고 방문을 표시할 때 들어가는 수는 현재 정점에 -1을 곱한 수이다.

현재 정점이 1이라면 -1이 들어가고 -1이라면 1이 들어간다.

 

이렇게 하는 이유는 하나의 정점에서 처음으로 다른 정점에 방문할 때는 현재의 정점과 다른 방문 표시를 가져야

이분 그래프라는 것이 성립하기 때문이다.

 

다음에 방문하고자 하는 정점이 방문을 이미 한 정점이라면 방문 표시 값을 확인한다.

만약 현재 정점의 방문 값과 다음 정점의 방문 값이 같다면 이 그래프는 이분그래프가 아니다.

 

아직 방문하지 않은 모든 정점들에 대해 BFS를 수행하면서 이분 그래프 여부를 확인한다.

만약 BFS 수행 결과 중에 이분 그래프가 아니라는 것이 한 번이라도 증명되면 이 그래프는 이분 그래프가 아니다.

 

[소스코드]

from collections import deque
import sys

def bfs(cur):
    queue = deque()
    queue.append(cur)
    visited[cur - 1] = 1

    while queue:
        v = queue.popleft()

        for i in graph[v - 1]:
            if visited[i - 1] == 0:
                queue.append(i)
                visited[i - 1] = visited[v - 1] * -1
            if visited[i - 1] != 0:
                if visited[i - 1] == visited[v - 1]:
                    return False

    return True


k = int(input())

for _ in range(k):
    isGraph = True
    v, e = map(int, sys.stdin.readline().rstrip().split())
    graph = [[] for _ in range(v)]
    visited = [0] * v

    for i in range(e):
        v1, v2 = map(int, sys.stdin.readline().rstrip().split())
        if v1 != v2:
            graph[v1 - 1].append(v2)
            graph[v2 - 1].append(v1)

    for i in range(1, v + 1):
        if visited[i - 1] == 0:
            isGraph = bfs(i)
            if not isGraph:
                break
    if isGraph:
        print("YES")
    else:
        print("NO")