[백준] 1707번: 이분 그래프 C++ - BFS, 큐를 사용하여 이분 그래프 판단하기.

https://www.acmicpc.net/problem/1707 문제를 좀 분석해 보자면 간선의 수는 200000, 정점의 수는 20000, 테스트 케이스 5개이다. 시간 복잡도는 꽤나 여유로워 보이니 문제를 분석해 보았다. 그래프를 두 집합으로 분할하되, 분할된 집합에서 인접하는 노드가 없게끔 분할하면 된다. 가장 먼저 떠오르는건 흐름은 다음과 같았다.시작점 start를 한 집합에 넣고, 인접한 점은 다른 집합에 넣는다.방문하지 않은 점 next에 대해 똑같이 1번을 수행한다.이렇게 떠올랐는데 굉장히 큰 오류들이 있었다.먼저 next는 첫 번째 단계의 start와 연관되어 있을 수 있었다. 즉, 맨 처음 시작점의 인접한 점과 그다음 방문하지 않은 점이 인접하다면? 인접하지 않다면? 모두 다른 방향으로..

2024.06.28