[Python]알고리즘/백준
[DFS/BFS/완전탐색] ★ 1707번 - 이분 그래프(BFS)
[백준] 1707번 - 이분 그래프 풀이 시간: 60분 이내 1) 문제 해결 아이디어 아이디어를 떠올리기 굉장히 어려웠던 문제다. 아이디어만 쉽게 떠올렸다면 구현하는데는 오래 걸리지 않은 문제다. 하지만 추후 복습이 필요한 문제! 일단 이분 그래프에 대해서 정확한 이해가 필요하다. 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 즉, 그래프의 정점을 두가지 색으로 칠한다고 했을 때, 인접한 정점끼리는 다른 색을 가지고 있는 그래프가 이분 그래프다. 1. 시작점 삽입, 방문 처리 (시작점은 0으로 방문 처리함) 2. 인접노드들에 대해 반복 2-1. 방문하지 않은 노드..
