[BOJ/python] 1707: 이분 그래프

문제

✔️ gold 4
그래프 이론
그래프 탐색
너비 우선 탐색
깊이 우선 탐색
이분 그래프

문제 흐름

처음에는 "두개 이상의 연결요소로 나누어질 수 있는 그래프"라고 생각했는데, 문제를 다시 잘 읽어보니 아녔다.
하나의 그룹 내에서 서로 인접한 노드가 없어야하니 어떤 노드 x가 1그룹이라면 이와 인접한 노드들은 전부 2그룹에 속해야한다.
또한 그래프가 2개 이상의 연결요소로 이루어져있다면 다른 연결요소 또한 위 규칙을 따라야 전체 그래프가 이분 그래프가 될 수 있다.
딱 이 포인트를 그대로 살려 코드화했다.

1. 테스트케이스별로 그래프를 입력받는다.
2. 그래프의 모든 노드에 대해서 3번을 진행한다.
3. 만약 해당 노드가 방문한 노드라면 그냥 넘어가고, 방문하지 않은 노드라면 BFS를 진행한다.

• BFS에서, 현재 노드 x와 그 인접 노드 nx의 방문표시가 같다면 바로 False를 리턴한다.
• BFS에서, 현재 노드의 방문표시가 1이라면 다음 노드는 2, 2라면 다음 노드는 1이 되도록 방문표시한다.

코드

# 이분 그래프
# graph

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

def bfs(g: list):
    v = len(g)
    vst = [0 for node in range(len(g))]
    for s in range(1, v):
        if vst[s]:
            continue
        q = deque([s])
        vst[s] = 1
        while q:
            x = q.popleft()
            xg = vst[x]
            nxg = 1 if xg == 2 else 2
            for nx in g[x]:
                if vst[nx] == xg:
                    return False
                elif vst[nx]:
                    continue
                q.append(nx)
                vst[nx] = nxg
    return True


if __name__ == "__main__":
    K = int(input())
    for testcase in range(K):
        V, E = map(int, input().split())
        g = [ [] for node in range(V+1) ]
        for edge in range(E):
            u, v = map(int, input().split())
            g[u].append(v)
            g[v].append(u)
        
        
        result = bfs(g)
        if result:
            print("YES")
        else:
            print("NO")

마무리

이전에 풀었던 코드가 있어서 살펴봤는데 함수로 쪼개놓은 것만 다르고 방식이 완전히 같았다.
역시 같은 사람이 푼 코드 ^^