백준 1707 이분 그래프

백준 1707 이분 그래프

---

오늘 문제로는 이분 그래프를 풀었다. 간단하게 생각해서 부모 노드의 집합과 자식 노드의 집합을 계속 번갈아 주면 된다.
A, B 집합을 번갈아 가며 주다가 만약 자식의 노드가 이미 방문한 상태에서 부모의 집합과 같다면, 이는 이분 그래프가 아니게 되는 것이다.

저 아이디어를 구현하는건 문제가 되지 않는다. 사실 생각하지 못했던 문제는 이 문제의 경우 간선들이 반드시 모두 연결되어 있진 않다는 것이다.
분리된 여러 개의 그래프가 존재할 수 있다. 그렇기 때문에 한번 DFS 를 돌린 후, 아직 방문하지 않은 정점이 있다면 그 점부터 또 DFS 를 구해주는 일을 반복해야 한다.
이 과정에서 시간초과가 발생했고 정말 여러번 틀린 후에 정답을 받을 수 있었다ㅋㅋ.

 public static void dfs_func(int v, List<List<Integer>> table, int [] visited) {
        Queue<Integer> q = new LinkedList<>();

        for (int node = 1; node <= v; node++) {
            if (visited[node] == 0) {
                q.add(node);           //1번 정점을 VIsited 1 로 하여 시작
                visited[node] = 1;
            }
            while (!q.isEmpty()) {
                int cur = q.peek();
                q.remove();

                for (int i = 0; i < table.get(cur).size(); i++) {
                    int next_c = table.get(cur).get(i);
                    if (visited[next_c] == 0) { // 아직 한번도 방문 안한점이라니까
                        q.add(next_c);
                        visited[next_c] = (visited[cur] * 2)%3;         // 1 이었음 2가, 2였으면 1이 들어갈 수 있도록 함.
                    } else {
                        // 여기서 만약 cur 의 visited 값과 next_C 로 배정되어야 할 값이 일치한다고 나오는 경우가 사고가 난 경우임.
                        if (visited[cur] == visited[next_c]) {

                            System.out.println("NO");
                            return;
                        }
                    }
                }
            }
        }
        System.out.println("YES");
    }

다음의 코드에서 node 를 1 부터 v 까지 순회하며 아직 방문하지 않은 노드일 경우 큐에 넣어 DFS 를 계속 반복해 주었다.
그 와중에 아까 이분 그래프의 성질을 만족하지 않는 경우가 발생했을 경우 바로 NO 를 출력해주었다.