이분 그래프 (1707번) - 백준 (BOJ)

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

1707번: 이분 그래프

 

 

백준 - 이분 그래프 (1707번)

 

난이도 : Gold 4

알고리즘&자료구조 : DFS (깊이 우선 탐색)

풀이 소요 시간 : 25분

 

 

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


def is_bipartite(v, e):
    def dfs(v, b):
        memo[v] = b
        for cv in graph[v]:
            if memo[cv] == b^1:
                continue
            if memo[cv] == b or not dfs(cv, b^1):
                return False
        return True
    
    
    memo = [-1] * (v+1)
    graph = [[] for _ in range(v+1)]
    for _ in range(e):
        v1, v2 = map(int, input().split())
        graph[v1].append(v2)
        graph[v2].append(v1)
    answer = all(dfs(i, 0) for i in range(1, v+1) if memo[i] == -1)
    return 'YES' if answer else 'NO'


if __name__ == '__main__':
    print('\n'.join(is_bipartite(*map(int, input().split())) for _ in range(int(input()))))

 

 

인접한 노드는 서로 다른 그룹으로 분류하는 문제이다.

 

---

 

① 임의의 노드를 루트 노드로 설정하고, DFS 를 시작한다.

(루트 노드는 어떤 노드라도 상관 없고, DFS 가 아닌 BFS 를 써도 된다.)

 

 

② 현재 노드의 값이 1 이라면, 자식 노드들의 값은 0 으로 할당하고,

현재 노드의 값이 0 이라면, 자식 노드들의 값은 1 로 할당한다.

현재 노드 1 → 자식 노드 0
현재 노드 0 → 자식 노드 1

 

 

③-ⓐ 만약 현재 노드가 0인데,

어떤 특정 자식 노드를 이미 방문한 적이 있고,

그 자식 노드의 값이 현재 노드와 동일하게 0 이라면

이 그래프는 이분 그래프가 될 수 없으므로, False 를 return 한다.

현재 노드 0 ↔ 자식 노드 0  ▶  이분 그래프 X
현재 노드 1 ↔ 자식 노드 1  ▶  이분 그래프 X

 

 

③-ⓑ 만약 위의 ③-ⓐ 과정에서 아무런 문제없이 DFS 가 종료된다면,

해당 그래프는 이분 그래프가 될 수 있으므로, True 를 return 한다.

 

 

④ 위의 ① ~ ③ 과정을 K 개의 테스트 케이스에 대해서 수행하고, 결과를 반환한다.

 

---

 

※ 그래프가 모두 연결되지 않고, 여러 부분 그래프로 나눠진 히든 케이스가 있으니

그것을 고려해서 코드를 구현해야 한다.