배움과 성장/알고리즘·문제풀이
백준 1707 Java: 이분 그래프를 BFS 2-Coloring으로 판별하기
백준 1707의 핵심은 graph의 모든 edge가 서로 다른 두 color를 잇도록 색칠할 수 있는지 확인하는 것이다. 처음 풀 때 이분 그래프의 정의가 선명하지 않아 약 일주일 동안 문제를 바라봤고, 결국 “인접한 두 vertex를 반대 색으로 칠한다”는 문제로 연결했다.이분 그래프와 2-Coloringvertex 집합을 두 group으로 나누고 같은 group의 vertex끼리는 edge가 없게 만들 수 있으면 bipartite graph다. 이를 color 1과 -1로 표현하면 모든 edge (u, v)에서 다음 조건을 만족해야 한다.color[u] != color[v]BFS로 한 vertex에 1을 주고 neighbor에는 -1, 그 neighbor의 neighbor에는 다시 1을 준다. 이미 ..