[Java] 1707 이분 그래프

문제

문제
그래프의 정점의 집합을 둘로 분할하여, 
각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 
그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 
이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 
첫째 줄에 테스트 케이스의 개수 K가 주어진다. 

각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고
순서대로 주어진다. 

각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 
이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데,
각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다. 

출력
K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

문제 풀이

BFS를 이용해야하는 문제이다.

이 문제에서 중요한 점은 이분 그래프에 대한 이해이다.

이분 그래프에 대한 이해력이 부족하여 풀이법을 생각하는 데 한 참 걸렸다...

이분 그래프를 설명하기 위해 예시를 하나 들겠다.

숫자 1 2 3 4 5 6 이 있다고 했을 때 숫자를 1,2,3을 한 집합, 4,5,6을 한 집합으로 한다고 해보자

즉 {1,2,3} {4,5,6} 두 그룹이 있다고 하는 것이다. 그리고 그룹에 상관없이 각 숫자들 끼리를 잇는 간선들이 있을 것이다.

이분 그래프는 각 그룹끼리의 숫자를 잇는 간선이 없는 그래프를 이야기하는 것이다.

만약 위의 그룹 예시에서 1과 2 혹은 4와 5를 잇는 등의 간선이 있다고 한다면 이 그래프는 이분 그래프가 되지 못하는 것이다.

 

이 부분을 이해하고 백준 해당 문제의 예시를 보도록 하자.

문제의 예시를 보면 아래 처럼 입력이 주어진다.

2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2

 

위를 입력별로 나누어 보자

2 // 테스트 케이스의 수

3 2 // 첫 번째 테스트 케이스의 정점 수와 간선 수
1 3 // 첫 번째 테스트 케이스의 간선 1
2 3 // 첫 번째 테스트 케이스의 간선 2

4 4 // 두 번째 테스트 케이스의 정점 수와 간선 수
1 2 // 두 번째 테스트 케이스의 간선 1
2 3 // 두 번째 테스트 케이스의 간선 2
3 4 // 두 번째 테스트 케이스의 간선 3
4 2 // 두 번째 테스트 케이스의 간선 4

두 번째 테스트 케이스를 기준으로 예시를 들어보겠다.

간선을 제공 받았는데 어느 것이 그룹 1이고 2인지는 입력을 받지 않았다.

그래서 그냥 입력받은 순으로 그룹이 나눠지지 않은 수라면 첫 번째 수를 1그룹, 두 번째수를 2그룹으로 생각해서 로직을 구현한다.

즉, 아래와 같이 구분한다.

1 2 -> 1그룹 : {1}, 2그룹 : {2}
2 3 -> 1그룹 : {1, 3}, 2그룹 : {2}
3 4 -> 1그룹 : {1, 3}, 2그룹 : {2, 4}

4 2  -> 1그룹 : {1, 3}, 2그룹 : {2, 4}

 

자 이제 각 간선 별로 검사를 하는 해보면 4 2에서 같은 2그룹끼리 이어지는 것을 볼 수 있다.

그렇기 때문에 해당 테스트케이스는 NO를 출력한다.

 

자세한 코드 로직에 대한 설명은 주석을 확인할 것.

자바 코드

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

public class N1707 {
    static int v, e;
    static ArrayList<Integer>[] link;
    static int[] visit;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stz = new StringTokenizer(br.readLine());
        int t = Integer.parseInt(stz.nextToken());

        for(int tc = 0; tc < t; tc++) {
            stz = new StringTokenizer(br.readLine());
            v = Integer.parseInt(stz.nextToken());
            e = Integer.parseInt(stz.nextToken());
            visit = new int[v + 1];
            link = new ArrayList[v + 1];

            // 입력받은 정점 수 만큼 리스트를 생성한다.
            // 리스트는 각 정점과 이어지는 다른 정점의 번호를 저장한다.
            for(int i = 0; i <= v; i++)
                link[i] = new ArrayList<>();

            // 입력받은 간선 수 만큼 간선을 입력 받는다.
            for(int i = 0; i < e; i++) {
                // p1과 p2는 간선으로 이어진다.
                // 서로를 리스트에 저장한다.
                stz = new StringTokenizer(br.readLine());
                int p1 = Integer.parseInt(stz.nextToken());
                int p2 = Integer.parseInt(stz.nextToken());

                link[p1].add(p2);
                link[p2].add(p1);
            }

            // 준비된 리스트를 이용하여 BFS를 진행
            bfs();
        }
    }

    public static void bfs() {
        Queue<Integer> q = new LinkedList<>();

        // 아직 그룹이 나누어지지 않은 정점이라면 1그룹에 지정하고 큐에 담는다.
        for(int i = 1; i <= v; i++) {
            if(visit[i] == 0) {
                q.add(i);
                visit[i] = 1;
            }

            // 큐가 빌때까지 실행
            while(!q.isEmpty()) {
                int now = q.poll();
                
                // 현재 큐에서 선택된 정점 리스트의 사이즈 만큼 반복
                for(int j = 0; j < link[now].size(); j++) {
                    // 해당 리스트와 연결된 다른 정점이 아직 그룹이 지정되지 않았으면 큐에 삽입한다.
                    if(visit[link[now].get(j)] == 0) {
                        q.add(link[now].get(j));
                    }

                    // 해당 리스트와 연결된 다른 정점이 같은 그룹이면 NO를 출력하고 종료한다.
                    if(visit[link[now].get(j)] == visit[now]) {
                        System.out.println("NO");
                        return;
                    }

                    // 해당 리스트의 그룹이 1일 경우 아직 그룹이 지정되지 않은 연결 그룹을 2그룹으로 지정하고
                    // 2일 경우 1로 지정한다.
                    if(visit[now] == 1 && visit[link[now].get(j)] == 0)
                        visit[link[now].get(j)] = 2;
                    else if(visit[now] == 2 && visit[link[now].get(j)] == 0)
                        visit[link[now].get(j)] = 1;
                }
            }
        }

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

}