BOJ_1707 : 이분 그래프

👉 문제링크

1707번: 이분 그래프

---

 

---

🔸 문제 분석 🔸

• 무방향 그래프가 주어지면, 이분 그래프인지 아닌지 판별한다.

🔸 문제 풀이 🔸

• 그래프 탐색을 통해 각 노드가 서로 다른 집합에 속하는지 구분한다.
  • DFS로 처음 방문한 노드에 한번은 A집합, 한번은 B집합으로 번갈아 가며 포함시킨다.
  • 이미 방문한 노드인데, 같은 집합이면 이분 그래프가 아니다.
• 여러 개의 부분 그래프로 이루어 져있을 수 있으므로, 모든 노드에서 DFS를 시작해본다.
  • 모든 탐색 이후 이분 그래프 판정 결과를 출력한다.

🔸 코드 🔸

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private static ArrayList<Integer>[] adjList;
    private static int[] check;
    private static boolean[] visited;
    private static boolean flag;

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = null;
        String sb = "";

        int K = Integer.parseInt(br.readLine());

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            check = new int[V + 1];
            visited = new boolean[V + 1];
            flag = true;

            adjList = new ArrayList[V + 1];
            for (int j = 1; j <= V; j++) {
                adjList[j] = new ArrayList<>();
            }

            for (int j = 0; j < E; j++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                adjList[a].add(b);
                adjList[b].add(a);
            }

            // dfs
            for (int j = 1; j <= V; j++) {
                if (flag)
                    dfs(j);
                else
                    break;
            }
            if (flag)
                bw.write("YES\n");
            else
                bw.write("NO\n");
        }

        // Output
        bw.write(sb);
        bw.flush();
    }

    private static void dfs(int node) {
        if (!flag) return;

        visited[node] = true;
        for (int i : adjList[node]) {
            if (!visited[i]) {
                check[i] = (check[node] + 1) % 2;
                dfs(i);
            } else if (check[node] == check[i]) {
                flag = false;
            }
        }
    }
}

🔸 코드 해석 🔸

• 노드를 재귀 메서드 dfs로 탐색하며, 처음 방문하는 인접 노드에 0 또는 1을 check배열에 저장한다.
• 만약 처음 방문한 노드가 아닌데, 같은 숫자이면 사이클이 발생 한 것이므로 이분 그래프가 아니다.

---

🔸 end 🔸

•  그래프를 두 집합으로 나눠야 한다고 해서 분리 집합(Disjoint Set)으로 Union-Find 메서드를 만들어야 하나 싶다가 BFS로 풀수 있을 것 같아 시도했더니 1회 틀렸다.
  • 알고보니 문제를 잘못 이해했는데, 아얘 왕복할 수 없는 집합을 나누는 것이 아니라, 직접 연결만 되어있지 않으면 되는 것이었다.
  • 이분 그래프를 아직 익숙하지 않아서 더 공부해야 될 것 같다.