[백준 1707] 이분 그래프 ❕

코뉴·2022년 1월 30일

백준🍳

목록 보기

88/149

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

🥚문제

🥚입력/출력

🍳코드

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


def bfs(start, visited):
    q = deque([start])
    visited[start] = "red"

    while q:
        u = q.popleft()
        for v in graph[u]:
            # 아직 방문하지 않음
            if visited[v] == "":
                if visited[u] == "red":
                    visited[v] = "blue"
                else:
                    visited[v] = "red"
                q.append(v)
            # 방문한 그래프라면
            # u와 v의 색깔이 같으면 안됨
            elif visited[v] == visited[u]:
                return "NO"
    return "YES"


K = int(input().strip())
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)

    """ graph print
    print("="*10, "graph", "="*10)
    for row in graph:
        print(row)
    """

    """ visited """
    visited = [""] * (V+1)

    """ bfs """
    # 모든 정점이 연결되어 있지 않을 수도 있으므로
    # 각 정점을 한 번 씩 검사해줘야 함
    for i in range(1, V+1):
        if visited[i] == "":
            ans = bfs(i, visited)
            if ans == "NO":
                # ans가 NO라면 바로 탐색 멈추고 프린트
                break
    print(ans)

🧂아이디어

그래프이론, 탐색

이분 그래프

정점을 두 그룹으로 나눌 수 있다고 할 때, 간선으로 연결된 두 정점이 서로 다른 그룹인 그래프

쉽게 말하면, 정점을 빨강과 파랑으로 칠할 수 있다고 할 때 간선으로 연결된 두 정점은 절대 같은 색일 수 없다

BFS

BFS로 탐색해간다.

정점 u과 연결된 정점 v를 방문할 때,
- 정점 v에 아직 방문하지 않은 상태라면
  - 정점 v를 정점 u와 다른 색으로 칠하고 BFS를 위해 큐에 정점 v를 삽입한다.
- 정점 v에 방문한 적이 있다면
  - 정점 u와 정점 v의 색깔이 같으면 안된다! (이분 그래프 위반)
  - 만약 색깔이 같은 경우에는 "NO"를 리턴한다.