그래프와 순회. [1707]

[1. 문제 설명]

주어진 그래프가 이분 그래프인지 아닌지 판별한다.

---

[2. 풀이 접근]

이분 그래프란?

그래프의 모든 정점이 두 그룹으로 나누어지고,

서로 다른 그룹의 정점들은 연결되지만(인접하지만),

같은 그룹의 정점들은 서로 연결되지 않는(인접하지 않지만) 그래프

 

 

인접한 정점은 서로 다른 그룹에 속해야 하므로

bfs 로 모든 정점을 순회하는데

바로 인접한 정점은 현재 정점과 무조건 반대 그룹에 속하도록 한다. 

(다른 그룹 번호를 할당)

그런데, 인접 정점이 이미 방문되었고, 그 그룹이 자신과 같은 그룹 번호라면

이 경우, 이분 그래프가 될 수 없다.

---

[3. 코드]