CodeAngie

문제 그래프의 정점을 두 집합으로 분할할 때, 인접한 정점끼리 서로 다른 집합에 포함되는 그래프를 이분 그래프라고 한다. 주어진 그래프가 이분 그래프인지 판별하는 문제이다. 풀이 이분 그래프인지 확인하기 위해서 정점들을 두 가지 색으로 칠할 때, 인접한 정점끼리 서로 다른 색으로 칠할 수 있는지를 확인하면 된다. 즉, 인접한 정점이 같은 색이라면 이분 그래프가 아닌 것이다. 예를 들어 a를 노란색(1)으로 칠한다면, a와 연결된 b,c,d를 초록색(2)으로 칠하는 것이다. 그 다음 b,c,d에 연결된 인접한 정점들을 다시 노란색(1)로 칠하다가 이미 다른 색으로 칠해진 정점을 만났을 때, b,c,d와 같은 초록색(2)이 칠해져 있다면 이분 그래프가 아니라고 판별할 수 있다. 반대로 모든 정점들을 방문해도..

인접한 노드(정점)끼리 서로 다른 색으로 칠해서 두 가지 색으로 분할할 수 있는 그래프를 이분 그래프라고 한다. 즉 각각의 집합에 속한 노드끼리는 서로 인접하지 않도록 분할하는 것이다. 시간복잡도: O(V+E) 1. 이분 그래프 알고리즘 BFS, DFS 를 사용하여 이분 그래프인지 여부를 확인 가능하다. 판단 방법 서로 인접한 노드가 같은 색이면 이분 그래프가 아니다. BFS, DFS로 노드를 방문할 때마다 두 가지 중 한가지 색으로 칠한다. (1 혹은 2) 이때 인접한 노드와는 서로 다른 색을 선택한다. 즉, 현재 노드의 색(1)과는 다른 색(2)으로 연결된 다음 노드를 칠한다. 여기서 0은 방문하지 않음을 뜻하고 1 혹은 2는 서로 다른 색을 뜻한다. $color_{next}= color_{befor..