[백준 2024/09/18] 1707번 이분 그래프

1. 문제

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

 

2. 접근 방법

처음에 이분 그래프 (Bipartite Graph)를 잘 이해하지 못하여 헤맸었다.

이에, 이분 그래프에 대한 설명을 찾아보게 되고 문제 풀이의 가닥을 잡게 되었다.

 

특정 노드에서 인접 노드로 접근하게 되면, color_num을 증가시켜서 넣어주는 방식으로 접근하였다.

빨간색, 검정색으로 표현하고 싶었지만, 짝수와 홀수로 표현하는 것이 더 코드 작성이 편리할 것이라고 생각이 들었다.

 

만약 색이 칠해진 노드에 다시 접근하게 된다면, 저장된 color가 짝수인지 홀수인지 확인하였고, 새로이 저장하고자 하는 값과 일치하는 . 지확인하였다.

일치하지 않는다면, 다른 색을 저장하려고 하게 되는 것이며, 이는 이분 그래프의 정의에 어긋나기 때문에, False를 반환해 주었다.

 

코드를 부분부분 확인해 보자.

    def add_edges(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

주어진 정점 u, v에 대해서 양쪽 노드에서 모두 접근 가능하도록 defaultdict에 append 해주었다.

 

def is_bipartite(self):
    for i in range(vertex):
        if not self.visited[i]:
            is_bip = self.bfs(i, 0)
            if not is_bip:
                return 'NO'

    return 'YES'

이후, is_bipartite 함수를 호출해 주었는데, 특정 노드 visited 여부에 따라 해당 노드부터 다시 bfs 함수를 호출하였다.

이렇게 한 이유는, 독립적으로 분리되어 있는 노드가 있을 수 있기 때문이고, 이를 고려하기 위함이다.

 

본격적인 bfs 함수를 확인해 보자.

def bfs(self, i, color_num):
    queue = deque([i])
    self.color[i] = color_num

    while queue:
        cur_v = queue.popleft()
        color_num = self.color[cur_v] + 1
        self.visited[cur_v] = True
        for v in self.graph[cur_v]:
            if self.color[v] != -1 and self.color[v] % 2 != color_num % 2:
                return False

            if self.color[v] == -1:
                self.color[v] = color_num
                queue.append(v)

    return True

우선 deque를 선언하여, 시작 노드를 추가해 주었다. 또한 색도 지정해 주었다.

현재 노드의 color + 1을 통하여, 인접 노드의 색을 지정해 주었다.

만약 

1. 처음 방문한 노드가 아니고
2. 저장되어 있는 값이 새로이 저장하고자 하는 값과 홀수, 짝수가 다르다면, 

False를 반환하여 주었다. [ 빨간색을 이미 저장한 노드에, 검정색을 칠하려는 것과 동일한 것 ]

queue.append의 경우 색을 지정하지 못한 vertex의 경우에만 append를 하여 불필요한 중복 계산이 되지 않도록 하였다.

 

처음에, 아래 부분이 헷갈려서 중복적으로 탐색을 하곤 하였다.

queue에 append 하는 것은 새로이 색을 입힌 노드에 대해서만 진행하는 것이다.

왜냐하면, 이미 색이 입혀져 있다면, 그 노드는 이미 queue.pop()으로 호출이 되어 주변 노드 탐색을 마친 상태이기 때문이다.

                if self.color[v] == -1:
                    self.color[v] = color_num
                    queue.append(v)

 

3. 코드

from collections import defaultdict, deque
class Graph:
    def __init__(self, vertex):
        self.vertex = vertex
        self.graph = defaultdict(list)
        self.color = [-1] * vertex
        self.visited = [False] * vertex

    def add_edges(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def bfs(self, i, color_num):
        queue = deque([i])
        self.color[i] = color_num

        while queue:
            cur_v = queue.popleft()
            color_num = self.color[cur_v] + 1
            self.visited[cur_v] = True
            for v in self.graph[cur_v]:
                if self.color[v] != -1 and self.color[v] % 2 != color_num % 2:
                    return False

                if self.color[v] == -1:
                    self.color[v] = color_num
                    queue.append(v)

        return True

    def is_bipartite(self):
        for i in range(vertex):
            if not self.visited[i]:
                is_bip = self.bfs(i, 0)
                if not is_bip:
                    return 'NO'

        return 'YES'


if __name__ == "__main__":
    test_case = int(input())
    for _ in range(test_case):
        vertex, edge = map(int, input().split())
        g = Graph(vertex)
        for i in range(edge):
            u, v = map(int, input().split())
            g.add_edges(u-1, v-1)
        print(g.is_bipartite())