TIL_6 | 이분그래프(Bipartite Graph) - BOJ 1707

code_sign·2021년 1월 4일

TIL boj 이분그래프

algorithm

목록 보기

3/4

BOJ의 1707번의 문제를 풀다가 이분 그래프를 알게 되었다. 처음 이 그래프를 접한 소감은 '이게 도대체 뭐지?!'하는 생각이 너무 많이, 오랫동안 들었기 때문에 정리를 한번 해보고자 여기에 남긴다!

이분 그래프란(Bipartite Graph)?

이분 그래프는 위 그림과 같은 구조를 지닌다. 즉, 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프이다.

나는 처음 이 말이 이해가 안되었었는데 내가 풀어서 이해한 말은 다음과 같다.

한 정점에서 간선으로 연결된 다른 정점으로 이동할 떄 현재 있는 정점의 색과 이동할 정점의 색이 다르고, 이 색들의 수가 2가지로 제한할 수 있는 그래프

내가 풀어본 BOJ 1707번 문제

import sys
input = sys.stdin.readline

n = int(input())
for _ in range(n):
    v, e = map(int, input().split())
    d = [[] for _ in range(v + 1)]
    for i in range(e):
        a, b = map(int, input().split())
        d[a].append(b)
        d[b].append(a)

    # 색이 다르게 표시(1, 2)
    color = [0] * (v + 1)
    check = False # 멈추는 요소
    for i in range(1, v + 1):
        if check:
            break
        if color[i] > 0: # 색은 1, 2만 들어감
            continue

        color[i] = 1
        l = [i]

        while l and not check:
            num = l.pop()
            color_check = 3 - color[num] # 1 또는 2가 되게 설정

            for x in d[num]:
                if color[x] == 0:
                    color[x] = color_check
                    l.append(x)
                elif color[x] == color[num]:
                    check = True
                    break

    print('NO' if check else 'YES')

color 변수는 index에 바로 접근하기 위해서 +1의 크기만큼 설정하고, 0으로 초기화했다. while문을 돌면서 color의 해당 index의 값이 0이면 처음 접근하는 것이니 color_check를 대입하고, 아니면서 현재 색과 같다면 이분 그래프가 아니라는 뜻이니 break해준다.

이분 그래프의 특성상 2가지 색만으로 표현을 해야하기 때문에 color_check 변수에 3을 현재 color 값으로 빼는 방법으로 풀이를 하였다. (현재 color 값이 2면 1이 되고, 1이면 2가 되기 때문에 확인할 수 있다.)

l 리스트를 deque자료형을 써서 할 수도 있었지만, 어떤 자료형에서 pop을 해도 같은 결과가 나와서 그냥 list를 썼다.

Today, Learned

배운점

이분 그래프라는 녀석과 처음 만나 개념을 알았다는 것!(색칠공부..)
DFS/BFS의 구동 방식에 대해 다시 한번 배울 수 있었다.
input()의 구동방식이 sys.stdin.readline()에 비해 속도가 느리다. 그래서 애초에 실수를 없애기 위해 input = sys.stdin.readline을 해놓고 똑같이 사용하면 실수가 없어진다!