[백준 1707] 이분 그래프 / 자바 / dfs

#문제         

레벨: G4
알고리즘: dfs 
풀이시간: 1시간
힌트 참조 유무:

https://www.acmicpc.net/problem/1707

---

#문제 풀이        

이분 그래프가 뭔지 모르는 분들을 위해 설명하겠다. 

형식상, 이분그래프의 정의를 먼저 보자면  "모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다.".

그림으로 더 쉽게 이해해보겠다.
1노드를 빨간색이라고 하면 그에 인접한 노드들은 모두 블루여야 한다.

 

그렇다면 3번 노드는 블루이기 떄문에 3번 노드에 인접한 노드들은 모두 레드여야 한다.

만약 아래 그림과 같이 4번 노드가 b라면, 3번 4번이 인접한데 같은 색상이므로 이분 그래프가 아니다.

이제 이해가 되는가?

 

그러면 우리가 코드로 해줄일은 명확하다.

1. 노드의 색이 없다면 부여하면서 방문한다.
2. 방문노드의 인접노드들의  색깔을 검사한다. 
   2- 1 인접노드와 방문노드의 색이 같다면 false
   2- 2 색이 없다면 1번부터 반복한다.

+) 주의해야 할 점
위 그래프가 연결그래프라면 dfs 시작점을 하나로  잡으면 모든 노드를 탐색 가능하다. 만약 {1} {2,3,4,5} 이렇게 되어있다면 노드1만 탐색하고 2,3,4,5에 색을 부여하지 못한다. 

문제에서 위 그래프가 연결그래프라고 말한적이 없기 때문에 우리는 모든 노드를 순회하면 dfs()를 호출해야 한다 

 

 

---

#풀이 코드      

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static boolean ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int nodeN = Integer.parseInt(st.nextToken());
            int lineN = Integer.parseInt(st.nextToken());
            ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
            for (int k = 0; k <= nodeN; k++) {
                graph.add(new ArrayList<Integer>());
            }
            int[] color = new int[nodeN + 1];

            for (int j = 0; j < lineN; j++) {
                StringTokenizer st1 = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st1.nextToken());
                int end = Integer.parseInt(st1.nextToken());
                graph.get(start).add(end);
                graph.get(end).add(start);
            }
            ans = true;

            // 모든 정점을 탐색하며 방문되지 않은 정점에서 DFS 시작
            for (int node = 1; node <= nodeN; node++) {
                if (color[node] == 0) {
                    dfs(graph, color, node, 1);
                }
            }

            if (ans) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }

    static void dfs(ArrayList<ArrayList<Integer>> graph, int[] colors, int now, int color) {
        colors[now] = color;
        ArrayList<Integer> nexts = graph.get(now);

        for (int next : nexts) {
            if (colors[next] == colors[now]) {
                ans = false;
                return; // 이분 그래프가 아님을 확인한 경우 더 이상 탐색하지 않음
            }

            if (colors[next] == 0) {
                dfs(graph, colors, next, 3 - color);
            }
        }
    }
}