🪴 Quartz 4.0

BOJ 1707 - 이분 그래프

3 min read

풀이

이분그래프에 대한 개념을 배웠으며 인접리스트를 활용한 BFS 역시 연습한 문제이다.

이분그래프란 인접하는 정점들이 서로 다른 그룹일 경우에 이분그래프라고 한다.

입력값이 각 간선정보를 주기 때문에 인접리스트 l 를 선언하여 각 정점마다 인접한 정점들을 리스트에 담아준다.

이후 그룹핑을 위한 group 리스트를 선언해준 뒤 BFS 를 실행한다.

시작점을 그룹1로 구분한 뒤 인접한 정점들 중 그룹핑이 되지않은 정점들에게 그룹-1로 구분해준다.

이를 반복하다가 만약 인접한 정점 중 현재 정점과 같은 그룹일 경우 이분그래프가 아니기 때문에 False 값을 반환한다.

이후 BFS 를 통해 반환받은 값을 통해 이분그래프 여부를 판단한 뒤 출력조건에 맞게 출력하면된다.

소스코드

# 이분 그래프
from collections import deque
import sys
input = sys.stdin.readline
 
def bfs(k):
    group[k] = 1  # 시작점을 그룹1로 선언
    q = deque()
    q.append(k)
    while q:
        x = q.popleft()
        for i in l[x]:  # x와 인접한 정점들 중
            if group[i] == 0:  # 그룹핑이 안되어있을 경우
                group[i] = -group[x]  # 그룹-1로 선언
                q.append(i)
            elif group[i] == group[x]:  # 인접한 정점인데 같은 그룹일 경우 이분그래프가 아님
                return False
    return True
 
for t in range(int(input())):
    v, e = map(int, input().split())
    l = [[] for _ in range(v+1)]  # 인접리스트 선언
    group = [0] * (v+1)  # 두개의 그룹으로 나누기
    isBin = True
 
    for _ in range(e):
        a, b = map(int, input().split())  # 인접리스트로 저장
        l[a].append(b)
        l[b].append(a)
 
    for k in range(1, v+1):
        if group[k] == 0:  # 아직 그룹핑이 안된 정점들일 경우
            if not bfs(k):
                isBin = False
                break
 
    print("YES" if isBin else "NO")

References

Graph View