문제 : https://www.acmicpc.net/problem/1707

이분 그래프란?

이미지 출처 : https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

이분 그래프란 서로 인접하지 않는 두 그룹으로 나눌 수 있는 그래프를 말한다.

풀이

DFS와 BFS 두가지 방법으로 풀 수 있는데, 여기서는 BFS를 사용할 것이다.

예시 1 (YES)

1번 노드부터 시작한다.

1번 노드와 인접한 노드는 2번, 4번이므로 반드시 서로 다른 집합에 들어있어야 한다.

1. 2번 노드와 4번 노드의 집합이 고정되었으므로, BFS 큐에 2번과 4번을 넣고 다음 순서인 2번을 확인한다.
2. 2번과 인접한 노드는 1번, 3번이므로 자신의 집합에 1번과 3번이 있는지 확인한다.
3. 자신의 집합에 없는 것을 확인했으므로 자신과 인접한 노드들을 반대쪽 집합에 집어 넣으면 된다.

1. 1번 노드는 이미 방문했으니 확인할 필요가 없고, BFS 큐에 3번 노드만 넣고 다음 순서인 4번을 확인한다.
2. 4번과 인접한 노드는 1번, 3번이므로 자신의 집합에 있는지 확인한다.
3. 집합에 없고, 나머지 노드를 모두 방문했으므로 그냥 다음 순서로 진행한다.
4. 다음 순서인 3번 노드에서도 1~3 과정을 통해 문제가 없는 것을 확인한다.

모든 순서를 끝날 때까지 조건에 걸리는 경우가 없었으므로 이분 집합이라 할 수 있다.

예시 2 (NO)

예시 1과 동일한 과정으로 진행한다.

여기서 문제가 생기는데, 2번의 인접 노드인 4번 노드가 같은 집합에 들어있다.

이러한 경우가 발견되면, 이분 집합으로 나누는 것이 불가능하므로 즉시 NO를 출력하고 함수를 빠져 나오면 된다.

코딩

각 노드별로 인접한 노드를 저장하는 2차원 리스트를 만들면 다음과 같이 된다. (0번 인덱스는 버리는 공간) graph = [[], [2, 4], [1, 3], [2, 4], [1, 3]]

해당 노드를 방문했는지 아닌지, 방문 했다면 어떤 그룹에 속하는 지 나타내는 체크 리스트를 만든다. (0번 인덱스는 버리는 공간) visited = [False, False, False, False, False]

False면 미방문, 서로 다른 그룹은 1, -1 등 자유롭게 정해서 저장하자.

이제 1번 노드부터 4번 노드까지 반복하는 for loop를 돌면서, 방문하지 않은 노드라면 BFS를 호출하면 된다.

코드

# https://www.acmicpc.net/problem/1707

from collections import deque
import sys
input = sys.stdin.readline


def BFS(start, group):
    que = deque([start])
    visited[start] = group

    while que:
        node = que.popleft()

        for link_node in graph[node]:
            if not visited[link_node]:
                que.append(link_node)
                visited[link_node] = -visited[node]
            elif visited[link_node] == visited[node]:
                return True

    return False


if __name__ == "__main__":
    K = int(input())

    for _ in range(K):
        V, E = map(int, input().split())

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

        visited = [False] * (V+1)

        for i in range(1, V+1):
            if not visited[i]:
                result = BFS(i, 1)
                if result:
                    print("NO")
                    break
        else:
            print("YES")