백준 1707. 이분 그래프 (파이썬)

문제

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

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

 

해설

진짜 역대급으로 삽질했던 문제인 것 같다. 결론부터 말하면 이분 그래프는 dfs나 bfs로 풀 수 있다. 여기서는 dfs로 풀어보기로 한다.

먼저, 이분 그래프가 무엇인지와 dfs가 무엇인지부터 짚고 넘어가보자.

 

1) 이분 그래프란?

- 문제만 보고서는 솔직히 무슨 소리인지 이해가 되질 않았다. 그래서 한참을 문제를 보고 이해하려고 하다가, 결국은 검색으로 해결하였다. (앞으로 문제가 조금 더 친절해졌으면 좋겠다..)

우선은 이분 그래프라는 것은 자신과 이어져있는 노드들은 현재 자신의 색깔과 모두 다른 색깔로 표현되어야 한다. 최종적으로 서로 인접하지 않도록 둘로 분할할 수 있다면 이분 그래프이다.

위 그림 역시 이분 그래프이다. 같은 색깔의 노드끼리 연결되어 있는 것이 없고, 코랄색과 파란색 노드들을 묶어서 둘로 만들 수 있기 때문이다. 

 

이분 그래프가 아니려면 어떻게 해야하는 것일까? 우선 위에서 언급했던 것처럼 연결되어 있는 노드들이 서로 같은 색일 경우 이분그래프가 될 수 없다.

이런 경우에는 2번 노드와 4번 노드가 연결되어 있는데, 서로 같은 색의 노드가 연결되어 있다. 이런 경우, 같은 색끼리 묶어서 분할을 해도 노드들끼리 서로 인접해있기 때문에, 이분 그래프의 조건에 어긋난다.

 

2) DFS란?

Depth First Search의 약자로, 깊이우선탐색이라고 하는 그래프 탐색 알고리즘이다. 그래프에서 노드를 깊이를 우선으로 탐색하는 것이다. 아래처럼 생긴 그래프가 있다고 했을 때, 깊이를 우선으로 탐색하므로 1 - 2 - 4 순서로 먼저 탐색하게 된다.

1 - 2 - 4를 탐색 후, 4는 아래로 연결된 자식 노드가 없기 때문에 더 이상 탐색을 하지 않고 2번 노드의 자식인 5번을 탐색한다. 5를 탐색하면 5의 자식 노드가 없기 때문에 1의 자식 노드인 3을 탐색하게 되고, 그 다음 6 7 노드를 탐색하게 된다. 따라서 순서는, 1 - 2- 4 - 5- 3 - 4- 5 순서로 탐색을 하게 된다.

 

아래 동영상을 참고하면, 애니메이션으로 볼 수 있다. (사실 허접하게 직접 만들어서 업로드했던 영상이다....)

https://www.youtube.com/watch?v=Hzq5ziaS_Ic 

 

3) 알고리즘 풀이

본격적으로 알고리즘 풀이를 해보자. 이번 문제는 엄청난 삽질을 거쳤다.. 먼저 코드를 보자

import sys
sys.setrecursionlimit(10 ** 6)

K = int(input())

for _ in range(K):
    V, E = [int(x) for x in sys.stdin.readline().split()]

    nodes = [[] for _ in range(V)]
    visited = [0] * V

    for _ in range(E):
        u, v = [int(x) for x in sys.stdin.readline().split()]
        nodes[u - 1].append(v - 1)
        nodes[v - 1].append(u - 1)


    def search(node_idx):
        for v in nodes[node_idx]:
            if visited[v] == 0:
                if visited[node_idx] == 1:
                    visited[v] = 2
                elif visited[node_idx] == 2:
                    visited[v] = 1
                s = search(v)
                if not s:
                    return False
            elif visited[node_idx] == visited[v]:
                return False
        return True

    result = True

    for i in range(0, V):
        if visited[i] == 0:
            visited[i] = 1
            result = search(i)
            if not result:
                break

    print("YES") if result is True else print("NO")

- 문제 풀이 -

먼저, nodes라는 2차원 리스트안에 자신의 인덱스에 연결된 노드들을 넣어준다.

그 후에 visited 리스트를 선언을 해준다. visited 리스트는 노드를 방문했는지 안했는지 여부를 체크한다. 동시에 해당 노드가 무슨 색깔로 채워졌는지 체크할 것이다. 0은 방문을 안한 상태, 1은 코랄색, 2는 파란색으로 체크할 것이다.

 

그리고 1번 노드부터 탐색을 시작할 것이다. 탐색은 search 함수를 통해 할 것이다.

def search(node_idx):
        for v in nodes[node_idx]:
            if visited[v] == 0:
                if visited[node_idx] == 1:
                    visited[v] = 2
                elif visited[node_idx] == 2:
                    visited[v] = 1
                s = search(v)
                if not s:
                    return False
            elif visited[node_idx] == visited[v]:
                return False
        return True

node_idx는 노드의 번호이다. nodes 리스트의 node_idx에 있는 리스트 (연결된 노드들)에서 v로 하나씩 꺼내면서 반복문을 돌것이다.

1번 노드부터 탐색을 시작할 것이므로 search(0)을 호출해줄 것이다. 이유는 1번 노드는 리스트의 인덱스 상에서 0번일 것이기 때문이다.

먼저 1번 노드는 방문을 하였으므로 visited[0] = 1로 채워주고 시작한다.

 

search 함수에 node_idx = 0으로 들어오면 nodes[0]에는 [1, 2]가 있다. (2,3 노드가 연결되어 있다는 뜻)  nodes[0]에서 for문을 돌면 처음 v에는 1이 들어간다. visited[1] = 0이므로, visited[0]의 색깔에 따라서 visited[1]의 색을 채워줄 것이다. 현재 visited[0]에는 1이 들어가 있으므로, visited[1]은 2로 채워준다.

색을 채워준 후에는, search()를 한번 더 호출해준다. 이 때, 현재 v를 파라미터로 전달한다. 따라서 search(1)이 호출된다.

search(1)이 호출되었으므로, 이번에는 node_idx = 1이 된다. 현재까지 재귀함수 호출 상태를 보면 아래 그림과 같다.

 

다시 돌아와서, node_idx = 1이므로, 이번에는 nodes[1]의 리스트에서 반복문을 돌 것 이다. nodes[1]에는 [0]이 들어가있으므로, visited[0]을 체크하는데, visited[0]은 이미 방문해서 visited[0]에는 1이라는 값이 들어 있으므로, 현재 node_idx인 1, 즉 visited[1]과 visited[0]의 색깔이 같은지 체크해준다. 같지 않으므로, 이분 그래프의 법칙에는 위배되지 않는다. 따라서 True를 return 해준 후, 다시 search(0)으로 돌아온다.

node_idx가 0일 때로 다시 돌아왔으므로, nodes[0]에서 돌던 반복문을 마저 돌게 된다. nodes[0]에서 1은 방금 방문하고 왔고, 2를 방문할 차례이다. visited[2] = 0이므로, visited[0]에 1이 들어가 있으므로, visited[1]에 2를 넣어준다.

색을 넣었으므로, search(2) 함수를 호출한다. search(2)를 호출했으므로, node_idx = 2가 되고, nodes[2]에는 [0]이 들어있으므로, [0]에서 반복문을 돈다. 그런데 visited[0]은 이미 방문한 노드이므로, visited[0]과 visited[3]이 같은지 확인한다. 같지 않으므로 다시 반복문을 도는데, nodes[2] = [0]이므로 더이상 반복문을 돌 수 없다. 따라서 True를 return한다.

 

결과 적으로 이 그래프는 True를 리턴하게된다. 따라서, "YES"를 출력하게된다.

print("YES") if result is True else print("NO")

만약 중간에, visited를 비교했을 때 같은 색이라면 이분 그래프가 될 수 없으므로 False를 return해서 "NO"를 출력하게 된다.

 

- 삽질 포인트 -

1. 시간 초과

우선 시간 초과가 나서 고쳤던 부분이 있는데 바로, [int(x) for x in sys.stdin.readline().split()] 이부분이다. 입력을 받는 부분인데, 이 부분을 처음에는 map(int, input().split())으로 받았었다. 이 부분 때문에 시간 초과가 날거라고 생각을 못했었는데, input을 [int(x) for x in sys.stdin.readline().split()] 으로 받도록 바꾸니, 시간 초과가 해결되었다. 왜 그런지는 아직 잘 모르겠다..... 이제 그냥 입력을 readline()으로 받기로 했다.

 

2. 재귀함수 스택 용량 초과

그리고 문제를 dfs로 풀다보니 재귀함수로 구현하게 되었는데, RuntimeError(Recursive Error)가 났다..... 스택에 초과로 함수가 쌓여서 그런듯 했다... 그래서 구글링을 거쳐서 sys.setrecursionlimit(10 ** 6) 코드를 추가해줘서 해결되었다.

 

3. search() 호출

처음에는 단순히 모든 그래프들이 다 연결되어 있을거라는 생각으로, search(0)만 호출했다. 그런데, 답이 틀려서 생각을 해보니, 그래프가 모두 이어져있다는 보장이 없었다. 위에서 봤던 이런 그래프도 예시로 나올 수 있는 것이다.

그래서 for문으로 전체 노드를 돌면서 출발 지점을 설정해주었다. 단, 이미 방문했던 노드는 방문하지 않고 방문을 하지 않았던 노드들만 다시 출발을 시작하도록 해주었다.

for i in range(0, V):
        if visited[i] == 0:
            visited[i] = 1
            result = search(i)
            if not result:
                break