이분그래프1

• 

  백준 1707 java 이분그래프 (그래프) 이분그래프에 대한 정의를 이해 하지 못해서 한 1주일 정도는 그냥 바라본 문제다. 답지를 보기에는 골드4라는 티어 때문에 용납이 되지 않았고 금방 풀 수 있을 것 같아서 뚫어져라 쳐다 봤다. 결국 두색 칠하기 문제로 귀결되는 듯 보였다. 1. 인접한 두 수는 다른 색, 다른 숫자, 다른 그룹으로 짝지어 질 수 있는가 2. 그렇다면 조합으로는 안되나? => 조합으로는 시간 복잡도가 터질 수 있음 3. dfs 또는 bfs를 돌리며 색칠해 나가다가 인접한 정점이 같은 색깔 또는 같은 숫자인지를 보면 되겠구나 4. 간선이 연결되지 않은 정점들은 어떻게 처리하지? 5. 간선이 연결되지 않은 정점들은 또 dfs 또는 bfs를 돌리면서 집합을 두 집합으로 만들면 되겠구나! 1번 집합 2번 집합이 나오면 3번 집합/4.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 6. 15.