[Leetcode] 785. Is Graph Bipartite?

문제 : https://leetcode.com/problems/is-graph-bipartite/

---

인접한 노드의 색을 현재 노드의 색과 다른 색으로 칠해가면서 너비우선탐색을 진행한다. 칠할 수 있는 색은 두가지이다.

인접한 노드에 색이 칠해져 있지 않다면 현재 노드의 색과 다른 색으로 노드를 칠하고 칠한 노드를 탐색한다.

인접한 노드에 이미 색이 칠해져 있다면 현재 노드의 색과 비교한다 현재 노드의 색과 다른 색이면 유효한경우이다. 현재 노드의 색과 같은 색이면 유효하지 않으므로 false를 반환한다.

 

[그림 1]

시작노드를 첫번째 노드만으로 잡고 너비우선탐색을 한 번만 진행한다면 [그림 1]과 같이 3~6번 노드의 유효성은 체크할 수 없다.

모든 노드를 시작지점으로 잡고 위 방법으로 노드들을 탐색하되 노드의 색 배열은 매번 초기화 시키면 안된다.

 

시간복잡도는 O(N). N = 노드의 수

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/785.%20Is%20Graph%20Bipartite%3F.cpp