[JAVA] 백준 1707번 【G4.이분 그래프】

문제

1707번: 이분 그래프

 

풀이

1️⃣ 이분 그래프의 정의와 bfs 를 이용한 풀이

예전에 풀어봤던 문제여서, 원리를 쉽게 파악할 수 있었다.

 

이전에도, 한참을 고민했었다가 서칭해서 풀었었는데, 이분 그래프라는 단어가 나오면 이 정의를 생각해야한다.

 

이분 그래프인지 아닌지 확인할 수 있는 특징 중 하나인,

 

노드 그래프를 2개의 색깔로 칠했을 때, 인접하는 노드끼리 색이 겹치지 않게 색칠할 수 있을 때, 이분 그래프가 될 수 있다고 한다.

 

위와 같은 그림처럼 말이다.

 

아직 방문하지 않은 노드라면 1로 체크해두고 bfs 방식으로 주변 노드를 탐색하여 -1로 표시하게끔 하였다.

 

그렇게 모든 노드를 표시해놓고, 다시 모든 노드를 순회하여 주변 노드에 다른 숫자로 마킹되어있는 노드가 있다면 이분 그래프가 아님을 알 수 있다.

 

public class Main {
    static int V;
    static int[] checked;
    static Queue<Integer> q;
    static List<List<Integer>> nodes;

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

        while (K-- > 0) {
            String[] input = br.readLine().split(" ");
            V = Integer.parseInt(input[0]);
            int E = Integer.parseInt(input[1]);

            nodes = new ArrayList<>();

            for (int i = 0; i < V; i++) {
                nodes.add(new ArrayList<>());
            }

            while (E-- > 0) {
                input = br.readLine().split(" ");
                int u = Integer.parseInt(input[0]) - 1, v = Integer.parseInt(input[1]) - 1;
                nodes.get(u).add(v);
                nodes.get(v).add(u);
            }

            checked = new int[V];
            q = new LinkedList<>();

            for (int i = 0; i < V; i++) {
                if (checked[i] == 0) {
                    q.offer(i);
                    checked[i] = 1;
                    bfs();
                }
            }

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


        }

    }

    private static boolean checkBipartite() {
        for (int i = 0; i < V; i++) {
            List<Integer> connects = nodes.get(i);
            int color = checked[i];
            for (int connect : connects) {
                if (checked[connect] == color) {
                    return false;
                }
            }
        }
        return true;
    }

    private static void bfs() {
        while (!q.isEmpty()) {
            int u = q.poll();
            List<Integer> connects = nodes.get(u);
            for (int connect : connects) {
                if (checked[connect] == 0) {
                    checked[connect] = checked[u] * -1;
                    q.offer(connect);
                }
            }
        }
    }
}

 

결과

 

이분 그래프인지 아닌지를 판단할 수 있는 정의를 잘 기억해놓고 있어야겠다.