알고리즘 풀이 - 백준 1707(이분 그래프, 그래프(DFS, BFS))
관련글 그래프 관련 포스팅은 여기를 참조 이분 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 그래프가 이분 그래프인지 여부를 판별하는 문제 2. 풀이 이분 그래프는 아래와 같이 2 그룹으로 나누었을 때, 같은 그룹은 서로 인접하지 않아야 한다. 위의 그림과 같이 빨간 그룹과 파란 그룹이 있는데 같은 그룹은 인접하여 연결되지 않았다. 이런 경우 이분 그래프라고 할 수 있다. 이를 구하는 방법은 그래프를 탐색하며 인접한 정점들이 같은 속성(보통 색깔로 표현)을 가지지 않는지를 검사하면 된다. 기본적으로 탐색을 수행하면서 현재 탐색 중인 정점의 색상을 지정하고, 그것..