[백준] 1707번 이분 그래프 (Python)

정답 코드 및 풀이는 맨 아래에 있습니다.

https://www.acmicpc.net/problem/1707

 

• 이분 그래프의 개념만 익힌다면 수월하게 구상, 구현할 수 있다.

---

< 이분 그래프 > 

[문제]

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

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

[입력]

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

[출력]

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

[제한]

 

• 2 ≤ K ≤ 5
• 1 ≤ V ≤ 20,000
• 1 ≤ E ≤ 200,000

예제 입력	예제 출력
2 3 2 1 3 2 3 4 4 1 2 2 3 3 4 4 2	YES NO

---

아이디어

우선 이분 그래프라는 것을 이해해야 한다. 문제에 다음과 같이 나와있다. 이게 무슨 의미냐하면

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

사진 출처 : https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

다음 그림처럼 인접하지 않은 노드그룹 두 개로 나눌 수 있는 그래프가 이분 그래프이다.

즉, 인접한 노드끼리는 다른 그룹에 속하게 할 수 있다면 그 그래프는 이분 그래프인 것이다. 따라서 노드에 하나씩 접근할 때마다 이전에 접근한 노드와 다른 그룹을 배치시켜 주면 된다. dfs와 bfs 모두 풀 수 있는 문제 같다. 나는 bfs만 풀어왔기 때문에 dfs연습할 겸 dfs로 풀었다.

풀이 및 코드

import sys
sys.setrecursionlimit(1000000)

def dfs(now):
    for next in graph[now]:
        # 아직 접근 안했으면 접근
        if visited[next] == 0:
            # 반대되는 색 칠해줌
            visited[next] = -1 * visited[now]
            # dfs를 하나 더 호출하고, 만약 그 호출한 함수가 False를 리턴한다면 지금 이 함수도 False 리턴.
            if not dfs(next):
                return False
        # 인접한 점이 같으면 잘못된 것. -> False 리턴
        elif visited[next] == visited[now]:
            return False
    return True

k = int(sys.stdin.readline())
for _ in range(k):
    # 초기 세팅
    v, e = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(v + 1)]
    # visited에는 1 혹은 -1로 색 구분함
    visited = [0 for _ in range(v + 1)]
    for _ in range(e):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)
    # 모든 노드에 접근
    for i in range(1, v + 1):
        if visited[i] == 0:
            # 아직 접근 하지 않았다면 1로 설정(임의로 아무거나 설정하는 것임.)
            visited[i] = 1
            if not dfs(i):
                print("NO")
                break
    else :
        print("YES")

dfs 함수는 한 노드에서 접근하지 않은 인접한 노드가 더 이상 없을 때까지 계속해서 접근하고, 접근할 때마다 이전의 노드와는 다른 색을 칠해주는 함수이다. 두 개의 분리된 그래프가 있을 수도 있다. 이럴 땐 두 그래프가 모두 이분 그래프라면 그 그래프는 이분 그래프이다. (같은 색 그룹끼리 묶어주면 서로 인접하지 않는 두 그룹으로 나뉘므로) 따라서 for문을 통해 모든 노드에 접근해 주는 것이다.

후기

나는 자꾸 시간초과가 뜨길래 알고리즘상에 오류가 있는 줄 알았다. 한 시간 넘게 고민한 끝에 입력이 너무 반복되어서 시간초과가 나는 것이라는 걸 깨달았다. 입력이 많을 땐 input()보다 sys.stdin.readline()으로 입력을 받는 것이 훨씬 빠르게 동작한다. 이 점 주의하자!