문제 유형 그래프, bfs 풀이 방법 도출 문제의 조건은 다음과 같습니다. 1. 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 2. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 서로 인접한 간선, 즉 직접적으로 연결된 정점끼리는 서로 다른 집합에 존재해야합니다. 집합은 2개 밖에 없으니 A집합과 B집합만 존재해야합니다. class Node { int cur; int color; Node (int cur, int color) { this.cur = cur; this.color = color; } } 같은 집합은 같은 color로 색칠을 해주면됩니다. 이 문제는 bfs를 응용해서 해결할 수 있습니다. bfs를 통해서 인접한 정점을 서로 다른 color로 색칠해줍니다.
