그래프이론

[백준, Java] 1707번 : 이분 그래프

🔗 문제 링크 https://www.acmicpc.net/problem/1707 🤔 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 😮 문제 해결 방법 이분 그래프는 문제에 나와 있는 것 처럼 정점끼리 이어진 그래프를 하나의 집합으로 보고 서로 연결된 정점끼리는 다른 두 그룹으로 속하게 하는 그래프를 말한다. 따라서, 이분 그래프를 판별하는 방법은 다음과 같다. 색칠되지 않은 모든 정점에 대해 BFS를 진행한다. BFS의 시작 정점을 임의의 색상으로 색칠한다. ..