이분 그래프1 [백준] 1707번 - 이분 그래프 [Java] https://www.acmicpc.net/problem/1707 1. 아이디어 BFS 알고리즘과 방문 체크를 응용해서 해결할 수 있다.2. 문제풀이 이분 그래프의 조건이 정점을 두 집합으로 분할했을 때, 각 집합의 정점끼리는 서로 인접하지 않아야 한다.(그래프가 두 개로 쪼개지는거 아니다.) 두 집합에 대해 한 집합의 정점을 빨간색, 다른 집합의 정점을 검은색으로 칠한다고 생각하면 이분 그래프를 만족하려면 빨간색과 검정색이 퐁당퐁당 나오는 그래프가 되면 된다. 구현은 BFS를 활용해서 그래프를 탐색하며 번갈아 색깔을 칠해주고 같은 색이 인접하게 칠해지는 경우 이분 그래프가 아닌 것으로 판단했다. 색을 칠하는 것이 방문 체크가 되므로 방문안한 노드를 WHITE, 색이 칠해진 노드는 RED 또는 BL.. 2025. 1. 6. 이전 1 다음
