백준 1707번: 이분 그래프

BOJ

백준 1707번: 이분 그래프

이분 그래프(Bipartite Graph)

그래프 정점의 집합을 둘로 나눴을 때, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프를 말한다. 즉, 그래프의 정점을 두 가지 색으로 칠할 때, 인접한 정점끼리는 다른 색을 가지고 있는 그래프이다.

접근

다른 그래프 문제를 풀 때 자주 사용하던 dfs를 이용해서 문제를 풀었다.

주의할 점!

연결 그래프가 아닐 수 있다.

평상시에 “dfs(1)”로 탐색을 시작하는데, 이 문제에서 그렇게 하면 연결되어 있지 않은 그래프에는 접근할 수 없으므로 정확한 결과 값을 구할 수 없다.

Wrong Solution

def dfs(vertex):
    visit[vertex] = True

    for next in graph[vertex]:
        if visit[next] == False:
            colors[next] = colors[vertex] * -1
            dfs(next)
            # if not dfs(next):
            #     return False
        elif colors[next] == colors[vertex]:
                return False
    return True

위 코드를 제출하면 결과 값이 정확하게 나오지 않는다. 재귀함수의 return을 제대로 이해하면 위에 있는 코드가 왜 틀렸는지 알 수 있다. 처음에 전역에서 호출된 dfs와 그 dfs가 호출한 dfs는 서로 다른 함수이다. 그렇기 때문에, return False를 하더라도 종료되는 것은 dfs의 전체 과정이 아니라 딱 현재 실행되고 있는 함수뿐이다. 에를 들어, A 함수에서 실행된 B 함수가 False를 반환했다고 해서 A도 False를 반환하는 것은 아니다. B 함수의 반환 값과 상관 없이 A는 계속 탐색을 진행하고 B 함수의 호출 값과 다른 True를 반환할 수도 있다.

Correct Solution

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

def dfs(vertex):
    visit[vertex] = True

    for next in graph[vertex]:
        if visit[next] == False:
            colors[next] = colors[vertex] * -1
            if not dfs(next):
                return False
            # dfs(next)
        elif colors[next] == colors[vertex]:
                return False
    return True

K = int(input())

for i in range(K):
    V, E = map(int, input().split())

    graph = [[] for _ in range(V+1)]
    visit = [False] * (V+1)
    colors = [1] * (V+1)

    flag = True

    for i in range(E):
        vertex_a, vertex_b = map(int, input().split())
        graph[vertex_a].append(vertex_b)
        graph[vertex_b].append(vertex_a)

    for i in range(1, V + 1):
        if visit[i] == False:
            flag = dfs(i)
            if not flag:
                break

    print("YES" if flag else "NO")

만약 sys.setrecursionlimit(10**9) 이 문장을 사용하지 않고 BOJ에 제출하면, RecursionError가 발생한다 재귀와 관련된 에러인데, Pyhon이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때 많이 발생한다. 최대 깊이는 sys.getrecursionlimit()을 이용해 확인할 수 있고, BOJ의 채점 서버는 최대 재귀 깊이가 1,000으로 되어 있다.