[백준/Python] 이분 그래프

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

1707번: 이분 그래프

이 문제를 풀기에 앞서 이분 그래프의 개념을 알고 가야 한다.

 

이런 식으로 정점의 색깔을 바꾸어 칠하면서 같은 색끼리 간선이 없는 경우 이분 그래프이다. 간선이 있다면 이분 그래프가 될 수 없다. 이것을 코드에 적용하면 문제를 풀 수 있다. 코드에서는 색상을 숫자로 표시하였다. (예 - 파랑은 1로, 빨강은 -1로)

 

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

def bfs(start):
    queue = deque([start])
    visited[start] = 1 # 시작점 그룹은 1로

    while queue:
        v = queue.popleft() # 현재 정점
        for i in graph[v]: # 현재 정점과 연결된 정점이
            if visited[i] == 0: # 방문하지 않았다면 현재 정점과 다른 그룹으로 지정
                queue.append(i)
                visited[i] = -visited[v]
            elif visited[i] == visited[v]: # 이미 방문한 정점이 같은 그룹이라면 False
                return False
    return True

K = int(input())
for _ in range(K):
    V, E = map(int, input().split())
    graph = [[] for _ in range(V+1)] # 연결 리스트
    visited = [0] * (V+1) # 방문한 정점 체크
    result = True # 이분그래프 여부

    for _ 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 visited[i] == 0: # 방문하지 않은 정점이면 bfs 수행
            if not bfs(i): # 이분 그래프가 아니라면 탐색 중단
                result = False
                break
    print('YES' if result else 'NO')

1. 필요한 정보를 입력받은 뒤 방문한 정점을 체크할 수 있는 visited와 이분그래프인지 확인할 수 있는 변수 result를 생성한다.

2. 모든 정점을 탐색한다.

    2-1. 아직 방문하지 않은 정점이라면 bfs를 수행한다.

    2-2. 시작점은 그룹을 1로 만들어주고 큐를 탐색한다.

    2-3. 현재 정점과 연결된 정점들을 가져와 연결된 정점을 방문하지 않았다면 다른 그룹으로 지정한다. 

    2-4. 연결된 정점이 이미 방문했고 현재 정점과 같은 그룹이라면 False를 리턴한다. (같은 그룹(=색상)인데 간선이 있는 것이므로)

    2-5. bfs 수행 결과가 False 라면 이분그래프가 아니므로 탐색을 중단한다.

3. 결과에 따른 출력을 해준다.