[정글 알고리즘] - [중] -백준 1707 - 이분 그래프-골드4

이 문제는 DFS로 정점을 번갈아 색칠하면서 판별하는 대표적인 이분 그래프 문제다. 핵심은 인접한 두 정점은 반드시 서로 다른 색이어야 한다는 조건 하나다. [Source](https://www.acmicpc.net/problem/1707)

문제 요약

그래프의 정점들을 두 그룹으로 나누되, 같은 그룹 안의 정점끼리는 서로 인접하지 않게 분할할 수 있으면 그 그래프를 이분 그래프라고 한다. 입력으로 여러 그래프가 주어질 때, 각각이 이분 그래프인지 판별하면 된다. 

항목	내용
입력	테스트케이스 K, 정점 수 V, 간선 수 E, 그리고 E개의 간선 정보
출력	이분 그래프이면 YES, 아니면 NO
핵심 판별 기준	인접한 두 정점의 색이 항상 달라야 함

이분 그래프를 쉽게 말하면

정점들을 두 팀으로 나눌 수 있고, 같은 팀끼리는 간선이 연결되지 않으면 된다.

팀 A

색 1로 칠한 정점들

팀 B

색 -1로 칠한 정점들

그래서 구현에서는 실제로 두 그룹을 만들기보다, 정점을 1과 -1 두 색으로 번갈아 칠할 수 있는지만 확인하면 된다.

왜 색칠로 판별할 수 있을까?

어떤 정점을 1로 칠하면, 그 정점과 연결된 모든 정점은 반드시 -1이어야 한다. 그리고 그 정점들과 연결된 다음 정점들은 다시 1이어야 한다.

1번 정점: 1
인접 정점들: -1
그 다음 인접 정점들: 1
그 다음: -1

이렇게 DFS나 BFS로 그래프를 따라가면서 색을 번갈아 칠하다가, 인접한 두 정점이 같은 색이 되는 순간 이분 그래프가 아님을 알 수 있다.

작은 그림으로 이해하기

예를 들어 아래 그래프는 이분 그래프다.

1 - 3 - 2

1번 정점

색 1

3번 정점

색 -1

2번 정점

색 1

연결된 정점끼리 색이 모두 다르므로 조건을 만족한다.

이분 그래프가 아닌 경우는?

대표적으로 홀수 길이 사이클이 있으면 이분 그래프가 될 수 없다.

 

1 - 2
|   |
3 --

삼각형처럼 3개의 정점이 서로 이어진 구조를 생각해보면, 1을 1로 칠하고 2를 -1로 칠한 뒤 3을 1로 칠해야 하는데, 그러면 1과 3이 서로 연결되어 있으면서 같은 색이 되어 버린다.

결론

인접한 두 정점의 색이 같아지면 즉시 NO

visited 배열이 아니라 색 배열로 본다

이 문제에서는 단순 방문 여부만으로는 부족하다. 방문했는지뿐 아니라 어떤 색으로 칠했는지까지 알아야 하기 때문이다.

visited = [0] * (v + 1)

의미는 다음과 같다.

0 : 아직 방문 안 함

1 : 첫 번째 색

-1 : 두 번째 색

즉, 이 배열은 단순 방문 배열이 아니라 방문 + 색 정보를 동시에 담고 있다.

DFS 함수 핵심 흐름

DFS에서 해야 할 일은 딱 세 가지다.

1단계

현재 정점을 현재 색으로 칠한다

2단계

인접 정점이 미방문이면 반대 색으로 DFS

3단계

이미 방문한 정점인데 같은 색이면 실패

코드 해설 포인트

def dfs(x, color):
    visited[x] = color

현재 정점 x를 현재 색으로 칠한다.

if visited[next_node] == 0:
    if not dfs(next_node, -color):
        return False

아직 방문하지 않은 정점이라면 현재 색의 반대 색으로 칠하면서 DFS를 이어간다.

if visited[next_node] == visited[x]:
    return False

이미 방문한 정점인데 현재 정점과 같은 색이면 이분 그래프 조건을 위반하므로 즉시 False를 반환한다.

왜 모든 정점에서 확인해야 할까?

이 문제에서 그래프가 연결 그래프라는 보장은 없다. 즉, 그래프가 여러 덩어리로 나뉘어 있을 수 있다.

1 - 2

3 - 4 - 5 - 3

만약 1번에서만 DFS를 시작하면 위쪽 덩어리만 검사하고, 아래쪽 삼각형 구조는 아예 못 본다. 그런데 아래쪽 덩어리는 이분 그래프가 아니다.

for i in range(1, v + 1):
    if visited[i] == 0:
        if not dfs(i, 1):
            is_bipartite = False

그래서 반드시 모든 정점에 대해, 아직 방문하지 않았다면 DFS를 시작해야 한다.

시간 복잡도

각 정점과 간선을 전체적으로 한 번씩만 확인하므로, 테스트케이스 하나당 시간 복잡도는 다음과 같다.

O(V + E)

정점 수와 간선 수가 꽤 크기 때문에, 이 문제에서는 인접 리스트 + DFS/BFS 조합이 정석이다. [Source](https://www.acmicpc.net/problem/1707)

헷갈리기 쉬운 포인트

실수 포인트	왜 틀리는가	올바른 처리
visited를 True/False로만 사용함	방문 여부만으로는 색 정보를 알 수 없음	0 / 1 / -1 로 관리
1번 정점에서만 DFS 시작	연결되지 않은 다른 컴포넌트를 놓침	모든 정점에 대해 검사
미방문 정점을 같은 색으로 칠함	인접 정점은 반드시 반대 색이어야 함	-color 사용
이미 방문한 정점의 색 비교를 안 함	충돌 상황을 놓쳐서 틀림	같은 색이면 즉시 False

정답 코드

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

def dfs(x, color):
    visited[x] = color

    for next_node in graph[x]:
        if visited[next_node] == 0:   # 아직 방문 안 함
            if not dfs(next_node, -color):
                return False
        else:
            if visited[next_node] == visited[x]:   # 같은 색이면 실패
                return False

    return True

k = int(input())

for _ in range(k):
    v, e = map(int, input().split())
    graph = [[] for _ in range(v + 1)]
    visited = [0] * (v + 1)   # 0: 미방문, 1/-1: 두 색

    for _ in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    is_bipartite = True

    for i in range(1, v + 1):
        if visited[i] == 0:
            if not dfs(i, 1):
                is_bipartite = False
                break

    if is_bipartite:
        print("YES")
    else:
        print("NO")

한 줄 요약

이 문제는 DFS로 그래프를 두 색으로 번갈아 칠해보고, 인접한 정점끼리 같은 색이 되는 순간 실패 처리하는 문제다.

마무리

이분 그래프 문제는 결국 “인접한 정점은 서로 다른 그룹에 있어야 한다”를 코드로 바꾸는 문제다.

그래서 그룹을 직접 나누는 대신 1과 -1 두 색을 번갈아 칠하면서 모순이 생기는지만 보면 된다.

그리고 이 문제에서 가장 자주 놓치는 포인트는 하나다. 그래프가 여러 덩어리일 수 있으므로 모든 정점에서 시작 여부를 확인해야 한다.