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

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

1707번: 이분 그래프

문제 풀이

먼저 이분 그래프란 그래프에서 두 개의 집합으로 나눴을 때 각 집합의 정점이 서로 연결되어 있지 않은 그래프를 말한다.

그림으로 보면 다음과 같은 그래프를 이분 그래프라 한다

이 문제를 풀기 위해선 이분 그래프의 정의 "각 집합의 정점이 서로 연결되어 있지 않은 그래프"에 포커스를 맞춰야 한다.

위 조건을 맞추기 위해선 각 노드별로 탐색하며 인접노드를 현재 탐색 중인 노드와 다른 집합으로 분류해 나가면 된다.

 

따라서 집합을 구분하기 위해 다음과 같은 그룹을 지정해줬다.

static final int groupA = 1;
static final int groupB = 2;

따라서 group의 1 또는 2의 값이 아닌 디폴트 값 0이라면 방문하지 않았음을 뜻하고 위에서 설정한 조건을 비교하기 위해 Queue를 사용한다.

Queue<Integer> q = new LinkedList<>();
int[] group = new int[V + 1];

for (int i = 1; i <= V; i++) {
    if (group[i] == 0) {
        q.add(i);
        group[i] = groupA;
    }
    ...

여기서 방문하지 않은 노드를 왜 groupA라고 정하는지 의문이 들 수 있다.

사실 큰 의미는 없고 B로 설정해도 된다. 초기에는 어떠한 노드도 그룹이 없기 때문에 분류를 할 수 없어 초기값 세팅이라고 생각하면 된다.

 

그러면 다른 노드를 탐색할 때 영향을 주는 것 아닌가?

전혀 영향을 주지 않는다.

다시 생각해보자. 우리는 인접 노드들을 현재 노드와 다른 그룹으로 세팅해 나간다. 하지만 위 코드의 조건식에서는 group[i]==0인 즉 방문하지 않은 노드에 대해 A그룹으로 설정하고 있다. 이 말은 첫 노드부터 시작해 인접 노드들의 그룹설정이 끝나고 동떨어진 다른 트리로 넘어갈 때 해당 트리의 초기 그룹을 설정하기 위함이다.

그래프는 트리보다 더 큰 범위의 개념으로 여러 트리가 하나의 그래프로 표현된다.

즉 다음과 같은 그래프의 형태를 대비해 각 트리의 초기 그룹값 세팅이라고 생각하면된다.

다음은 인접한 노드의 그룹을 현재 탐색 중인 노드의 반대되는 그룹을 설정하는 코드이다

while (!q.isEmpty()) {
    int now = q.poll();

    for (int adj : graph.get(now)) {
        if (group[adj] == 0) { // 방문하지 않은 인접노드는 현재 노드와 반대의 그룹으로 설정
            q.add(adj);

            if (group[now] == groupA)
                group[adj] = groupB;

            if (group[now] ==  groupB)
                group[adj] = groupA;
        }

        if (group[now] == group[adj]) { // 인접노드와 그룹이 같다면 이분그래프가 아님
            return false;
        }
    }
}

코드

package 백준;

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

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

        for (int i = 0; i < testCase; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());

            ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
            // init()
            for (int j = 0; j <= V; j++) {
                graph.add(new ArrayList<>());
            }
            for (int j = 0; j < E; j++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());

                graph.get(from).add(to);
                graph.get(to).add(from);
            }

            System.out.println(isBinaryTree(graph, V) ? "YES" : "NO");
        }
    }

    static final int groupA = 1;
    static final int groupB = 2;

    static boolean isBinaryTree(ArrayList<ArrayList<Integer>> graph, int V) {
        Queue<Integer> q = new LinkedList<>();
        int[] group = new int[V + 1];

        for (int i = 1; i <= V; i++) {
            if (group[i] == 0) {
                q.add(i);
                group[i] = groupA;
            }

            while (!q.isEmpty()) {
                int now = q.poll();

                for (int adj : graph.get(now)) {
                    if (group[adj] == 0) { // 방문하지 않은 인접노드는 현재 노드와 반대의 그룹으로 설정
                        q.add(adj);

                        if (group[now] == groupA)
                            group[adj] = groupB;

                        if (group[now] ==  groupB)
                            group[adj] = groupA;
                    }

                    if (group[now] == group[adj]) { // 인접노드와 그룹이 같다면 이분그래프가 아님
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

느낀점

처음 문제를 풀 때는 어려웠지만 이분 그래프의 대해 이해를 하고 다시 접근하니까 되게 간단하게 풀렸다.