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

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

 

코드

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


def bfs(edges, start, colors):
    q = deque([start])
    colors[start] = 1
    while q:
        now = q.popleft()
        for nx in edges[now]:
            if colors[nx] == 0:
                colors[nx] = colors[now] % 2+1
                q.append(nx)
            elif colors[nx] == colors[now]:
                return False
    return True


for _ in range(int(input())):
    answer = True
    v, e = map(int, input().split())
    edges = [[] for _ in range(v+1)]
    for _ in range(e):
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)

    colors = [0]*(v+1)
    for i in range(1, v+1):
        if colors[i] != 0:
            continue
        result = bfs(edges, i, colors)
        if result == False:
            answer = False
            break
    print("YES" if answer else "NO")

 

이분 그래프도 나름의 공식? 같은게 있었다

https://code-angie.tistory.com/20

[알고리즘] 이분 그래프 (Bipartite Graph)

해당 블로그를 참고해서 풀이했는데, 간단하게 설명하자면 BFS 또는 DFS를 수행하며 노드들에 색을 칠해서 인접한 노드들끼리 다른 집합으로 구분될 수 있는지 확인하는 것이다. 예를 들어, 1과 2가 인접해있다고 할 때, 1을 빨간색으로 칠했다면 2는 파란색으로 칠하는 식이다.

 

이렇게 색을 칠하며 그래프 탐색을 하는데, 만약 인접한 노드가 이미 나와 같은 색상으로 칠해져있다면 해당 그래프는 이분 그래프를 만들 수 없는 경우이다.

 

여기서 주의할 점은 그래프의 모든 정점이 연결되어 있다는 말이 없다면 모든 정점에 대해 BFS를 실행해봐야 한다는 것이다. 물론 이전 노드가 실행한 BFS에서 이미 탐색된, 즉 colors에 0이 아닌 수가 기록되어 있다면 그 노드에서는 더이상 탐색해보지 않아도 된다. 어차피 해도 그 이전의 BFS에서 탐색한 결과와 같은 결과가 나올 것이다. 

 

---

 

DFS/BFS에 살짝만 아이디어를 추가해서 풀면 되는 것인데 한 번에 못 풀은게 분하다

네부캠하느라 놓쳤던 알고리즘 공부 열심히 해야겠다....