[백준] 1707번 이분 그래프 - Python / 알고리즘 기초 2/2 - 그래프 1

ByungJik_Oh·2025년 4월 14일

Baekjoon Online Judge

[Baekjoon Online Judge]

목록 보기

105/244

💡 문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

💭 접근

이분 그래프를 그림으로 나타내면 다음과 같다.

이처럼 모든 정점에 대해 인접하는 다른 정점들과 서로 다른 두 그룹으로 나눌 수 있는 그래프를 이분 그래프라고 한다.

따라서, 그래프를 방문하면서 방문하지 않은(visited가 0인) 정점에 대하여 인접하는 다른 정점으로 이동할 때 현재 정점과 다른 정점으로 저장해야한다. (코드에선 1과 -1)

elif visited[num] == 0:
    visited[num] = -visited[start] # 부호를 반전시켜 그룹을 나타낸다.
    dfs(num)

만약 인접한 정점중 이미 방문했던 정점이라면(visited가 0이 아니라면) 현재 나의 그룹과 다른 그룹인지 체크하고 같은 그룹이라면 이분 그래프가 될 수 없으므로 ans를 False로 바꾼다.

if visited[num] != 0:
    if visited[num] == visited[start]: # 인접한 정점이 같은 그룹이라면
        ans = False

또한, 그래프가 나누어져 있는 경우가 있을 수도 있으므로 방문하지 않은 모든 정점을 시작으로 DFS를 호출해 주어야한다.

for i in range(1, V + 1):
    if visited[i] == 0:
        visited[i] = 1
        dfs(i)

📒 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(start):
    global ans

    for num in graph[start]:
        if visited[num] != 0:
            if visited[num] == visited[start]: # 인접한 정점이 같은 그룹이라면
                ans = False
        elif visited[num] == 0:
            visited[num] = -visited[start] # 부호를 반전시켜 그룹을 나타낸다.
            dfs(num)

k = int(input())

for _ in range(k):
    V, E = map(int, input().split())
    graph = [[] for _ in range(V + 1)]
    for _ in range(E):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
    visited = [0 for _ in range(V + 1)]
    
    ans = True
    for i in range(1, V + 1):
        if visited[i] == 0:
            visited[i] = 1
            dfs(i)
            if not ans:
                print('NO')
                break
    else:
        print('YES')