[파이썬]백준 1707 이분그래프

링크

백준 1707 이분그래프

처음엔 이분그래프가 정확히 뭔지도 모르고 만들 수 있는 노드의 조합을 백트래킹을 통해 구현한 후 Union-find 알고리즘을 통해 만들어진 노드의 조합이 연결되어 있는지를 검사하려 했으나 메모리에러로 장렬히 실패했다..

그 후 이분그래프를 검색해서 알아봤다. 이분그래프란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다.

따라서 해당 문제는 각 정점을 빨간색과 파란색으로 칠할 때 인접한 두 정점을 반드시 다른색으로 칠할 수 있는지를 알아내는 문제이다.

내경우엔 1과 -1로 색을 구분해주면서 bfs를 돌았다.
만약에 색칠이 안되어있는 정점을 만났을 경우 현재 정점과 반대되는 색을 칠해주고
만약 같은 색이 있는 정점을 만났을 경우 이분이 불가능한 경우이기 때문에 함수를 끝내줬다.

또한 애초에 연결이 되어있지 않은 2개 이상의 그래프가 주어질 수 있기 때문에 반복문을 통해 모든 정점에서 함수를 실행하도록 만들었다.

정답 코드

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

def bfs(start):
    q = deque()
    q.append(start)
    color[start] = 1
    while q:
        u = q.popleft()
        for v in G[u]:
            if color[v] == 0:
                color[v] = color[u] * -1
                q.append(v)
            elif color[v] == color[u]:
                return True # 이분불가능
    return False

for tc in range(int(input())):

    V, E = map(int, input().split())
    G = [[] for _ in range(V + 1)]
    for _ in range(E):
        u, v = map(int, input().split())
        G[u].append(v)
        G[v].append(u)

    color = [0] * (V + 1)
    ans = False
    for i in range(1, V + 1):
        if color[i] == 0:
            ans = bfs(i)
            if ans: # 이분불가능하면
                break

    if ans:
        print('NO')
    else:
        print('YES')

알게된 것👨‍💻

• 이분그래프