[백준] 1707번 이분 그래프

   해당 문제의 원문은 여기서 확인하자.

문제 이해

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

   첫째 줄에 테스트 케이스의 개수 K가 주어지고, 각 테스트 케이스의 첫째 줄에 그래프의 정점 개수 V와 간선 개수 E가 빈 칸을 두고 주어진다. 각 정점은 1번부터 V까지를 번호로 사용하고, 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 입력된다. 제한 사항은 다음과 같다.

 

• 2 ≤ K ≤ 5
• 1 ≤ V ≤ 20,000
• 1 ≤ E ≤ 200,000
• 이분 그래프가 맞으면 YES, 아니면 NO를 출력한다.

---

접근 방식

   DFS의 개념을 이용해 문제를 해결하였다. 문제의 설명은 잘 이해되지 않는 경우 이분 그래프의 개념에 대해 이해하고 가자.

   DFS를 이용해 탐색하는 정점들을 2가지 색을 이용해 색칠해 나갈 것이다. 이 과정에서 인접한 정점에 같은 색이 존재하는 경우 이분 그래프로써 유효하지 않은 것으로 판단하여 결과에 'NO'를 출력해 나간다. 예제를 통해 자세히 알아보자.

 

 

   우선 시작 정점인 1을 색칠한 후 1번 정점과 연결된 정점을 찾는다. 찾은 정점의 상태에 따라 행동이 달라지게 되는데 우선 찾은 정점이 처음 방문(색깔이 없는)하는 경우, 이전 정점과 다른 색을 칠한 뒤 해당 정점에 대해 DFS를 수행한다.

 

정점 2를 처음 방문하는 경우

 

   만약 찾은 정점이 이전 정점과 색깔이 같은 경우 해당 그래프는 이분 그래프로써 유효하지 않기 때문에 전체 DFS를 중단하고 결과로 'NO'를 출력한다.

 

정점 2가 같은 색인 경우

 

   찾은 정점이 이전 정점과 다른 색인 경우, 이미 방문한 적있으며 유효한 연결이기 때문에 이전 정점과 연결된 다른 정점을 찾아 DFS를 수행한다.

 

정점 2가 다른 색인 경우

   처음 예제의 진행과정은 다음과 같다. 결과적으로 예제는 유효한 이분 그래프이다.

 

 

   유효하지 않은 그래프의 진행과정은 다음과 같다. 4번과 1번 연결에서 문제가 발생한다.

 

정점 1과 정점 4의 색이 같아져 유효하지 않음

 

   다음과 같이 그래프가 끊어진 상태도 고려해야 한다.

 

---

코드

import java.io.*;
import java.util.*;

public class 백준1707번 {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer token;
    static int[] color;
    static boolean flag;
    static final int RED = 1, BLUE = 2;

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

        //테스트 케이스 수만큼 반복
        while (K-- > 0) {
            token = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(token.nextToken());
            int E = Integer.parseInt(token.nextToken());
            List<Integer>[] link = new List[V + 1];
            color = new int[V + 1];

            for (int i = 1; i <= V; i++)
                link[i] = new LinkedList<>();
            //입력된 연결관계는 양방향으로 저장
            for (int i = 0; i < E; i++) {
                token = new StringTokenizer(br.readLine());
                int s = Integer.parseInt(token.nextToken());
                int e = Integer.parseInt(token.nextToken());
                link[s].add(e);
                link[e].add(s);
            }
            //이분 그래프 유효 여부 판단
            flag = true;
            //그래프가 애초에 끊어져있는 경우도 고려
            for (int i = 1; i <= V; i++) {
                if (color[i] != 0) continue;
                //시작지점을 빨간색으로 색칠 후 DFS 수행
                color[i] = RED;
                DFS(link, i);
            }
            //버퍼에 결과를 저장, 이후 한 번에 출력
            bw.append(flag ? "YES\n" : "NO\n");
        }
        bw.flush();
    }

    public static void DFS(List<Integer>[] link, int num) {
        //현재 정점과 연결된 정점에 대해 반복 수행
        for (int i : link[num]) {
            //방문한 적이 없는 경우, 현재 정점과 반대의 색 색칠
            //이후 해당 정점에 대해 DFS 수행
            if (color[i] == 0) {
                color[i] = 3 - color[num];
                DFS(link, i);
            } else if (color[i] == color[num]) {
                //색이 같은 경우 이분 그래프가 될 수 없음
                flag = false;
            }
            //유효하지 않은 경우 DFS 탐색 종료
            if (!flag) return;
        }
    }
}