[백준] 1707: 이분 그래프 - Java (그래프 알고리즘)

목 차문제접근 방식풀이   문제      접근 방식   이분 그래프란? 정점들은 두 개의 그룹 중(빨강과 파랑) 하나에 속하고, 빨간색 정점은 빨간색 정점과 연결될 수 없고, 파란색 정점은 파란색 정점과 연결될 수 없다. 즉 같은 색이 연결이 된다면 그 그래프는 이분 그래프가 아니다. 간단히 말해서, 연결은 항상 다른 색의 정점으로만 이루어진다.    그래프를 두 그룹으로 정리해 본다면 아래 그림과 같이 정리가 되는 것을 볼 수 있다. 절대 같은 색상끼리 연결이 안 되는 모습을 보여준다.     이분 그래프?1. DFS 혹은 BFS 로 확인할 수 있다.2. 그래프의 모든 정점과 간선을 한 번만 탐색하므로, 시간 복잡도는 O(V + E) 이다.    BFS 풀이1. Queue에서 뺀 정점의 인근 정점을 확..

Algorithm/BackJun 2024.05.15