백준 자바 문제풀이 #1707

문제 링크

이분 그래프

골드 난이도 문제라 해결이 쉽지 않을 것이라 예상은 했다만

문제를 이해하는 단계부터 막힐거라고는 생각 못했다.

읽어도 도통 뭔소리인지 와닫지가 않아서 오늘도 책보고 풀까 하다가

출판사에서 동영상 풀이를 남겨놨길래 설명을 들어봤다.

음... 이전까지의 문제들은 복기하면서 다시 풀 수 있겠다 싶었는데

이번 문제는 자신이 없다.

일단 수업 갔다와서 다시 생각 좀해봐야겠다.

---

문제 예제를 그림으로 표현했다.

왼쪽 그래프를 보면 1과 2가 각각 3이랑 이어져 있다.

1이 A 그룹이라면 1과 이어진 3은 1과 다른 그룹이어야 하고

3은 2와 다른 그룹이어야 한다.

문제에서는 그룹의 수를 두 그룹으로 제한했으므로

각 정점이 속한 그룹은 순서대로 A A B 가 된다.

오른쪽 그래프를 보면 2와 3, 4가 각각 연결되며 사이클을 형성하므로

두 그룹으로 묶을 수 없다.

주어진 그래프가 사이클이 포함하는가 라고도 볼 수 있다.

처음에는 각 정점이 어느 그룹에 속하는지를 확인하기 위해

부울 배열을 사용하려고 했는데

책에서는 정수 배열로 만든 다음 홀짝을 판단하는 식으로 풀이했다.

만약 주어진 그래프가 이분그래프가 아니라고 판단되면

해당 그래프는 더이상 판별하지 않아도 되므로

isEven이라는 부울변수를 사용해 진행여부를 판단했다.

package Gold.G4;

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

public class G1707 {
    static ArrayList<ArrayList<Integer>> list;
    static boolean[] visited;
    static int[] check;
    static boolean isEven;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine());
        for (int i = 0; i < k; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());

            list = new ArrayList<>();
            visited = new boolean[V + 1];
            check = new int[V + 1];
            isEven = true; // 이분그래프인지 아닌지
            for (int j = 0; j <= V; j++) {
                list.add(new ArrayList<>());
            }

            for (int j = 0; j < E; j++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());

                list.get(u).add(v);
                list.get(v).add(u);
            }

            for (int j = 1; j <= V; j++) {
                if (isEven) {
                    DFS(j);
                } else {
                    break;
                }
            }

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

    static void DFS(int now){
        visited[now] = true;

        ArrayList<Integer> cur = list.get(now);
        for (int i = 0; i < cur.size(); i++) {
            if (!visited[cur.get(i)]) {
                check[cur.get(i)] = (check[now] + 1) % 2;
                DFS(cur.get(i));
            } else if (check[now] == check[cur.get(i)]) {
                isEven = false;
            }
        }
    }
}

자바 11 270836 KB 1028 ms

풀고나니까 딱히 어렵진 않았는데

문제 이해가 잘 안되서 바로 손놓은, 아쉬운 문제였다.