📚 1707 - 이분 그래프

이분 그래프

풀이

dfs, bfs 동시에 사용 가능할 때는 bfs를 사용하는 것이 좋다.

✔️ 문제 푸는 팁
먼저 이분 그래프란 무엇인가 하면
서로 인접한 정점이 같은 색이면 이분 그래프가 아니다.
사이클이 형성되면 안된다.
이분 그래프 특징 설명 잘되어 있는 곳

이 문제는 전형적인 bfs와 dfs로 풀리지만 한 가지 생각할 점이 있다.
➡️ 방문 표시할 때, graph[a] = b일 때 a는 파란색(-1) b는 빨간색(1) 이 칠해지도록 구현하면 된다.
➡️ 작성한 소스 주석풀고 돌려서 출력 결과를 통해 그림을 그리다보면 이해가 될 것이다.

소스

from sys import stdin as s
from collections import deque


def bfs(start, group, graph):
    cur_direction = 1
    queue = deque()
    queue.append((start, cur_direction))
    group[start] = 1

    while queue:
        node, cur_direction = queue.popleft()
        # print("현재 데이터 : ", node, "현재 그룹 : ", cur_direction)
        for cur_node in graph[node]:
            # 만약 group의 cur_node 인덱스 값이 0이라면 방문하도록
            if group[cur_node] == 0:
                group[cur_node] = -cur_direction
                # print("방문하게 됨, cur_node : ", cur_node, " cur_direction : ", -cur_direction)
                queue.append((cur_node, -cur_direction))
            elif group[cur_node] == cur_direction:
                # 이미 방문을 한 정점이 같은 그룹에 있는지 확인
                # print("이미 방문한 지를 확인한다. cur_node : ", cur_node, " cur_direction : ", cur_direction, "group[", cur_node,
                #       "] : ", group[cur_node])

                return False
                # 만약 현재 노드의 그룹 값과 같은 공간에 (방향이 같다면) False

    return True


k = int(s.readline())

for _ in range(k):
    v, e = map(int, s.readline().split())
    group = [0] * (v + 1)
    graph = [[] for _ in range(v + 1)]
    result = "YES"

    for idx in range(e):
        a, b = map(int, s.readline().split())
        graph[a].append(b)
        graph[b].append(a)

    for idx in range(1, v + 1):
        if group[idx] == 0:
            if not bfs(idx, group, graph):
                result = "NO"
                break

    print(result)

채점 결과