[Gold-4] 1707번 | 이분 그래프 | BFS | 자바(Java)

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

 

 

해당 백준 문제는 이분 그래프 판별 문제이다.

BFS, DFS 문제를 꾸준히 풀었다면 쉽게 풀이할 수 있을 것이다.

 

이분 그래프란?

: 그래프의 정점들을 두 개의 집합으로 나누었을 때, 각 집합에 속한 정점끼리는 서로 간선으로 연결되지 않으며

두 집합에 속한 정점들끼리만 간선으로 연결된다는 것.

 

(1) 정점 집합 분할 : 이분 그래프는 정점들을 두 개의 집합으로 나눌 수 있다.

즉, 집합 A와 집합 B가 있고, 각 간선은 집합 A의 정점과 집합 B의 정점 간에만 존재한다.

 

(2) 인접 정점  : 두 집합에 속한 정점들은 서로 인접해야 하며, 같은 집합에 속한 정점들끼리는 인접하지 않다.

 

 

 

---

이분 그래프인지 아닌지를 탐색하는 데에는 BFS, DFS 모두 활용할 수 있다.

그래프를 탐색할 때, 각 정점에 색을 칠해가면서 탐색한다.

예를 들어, 한 정점을 빨간색으로 칠하면, 그와 인접한 정점은 파란색으로 칠한다는 것이다.

이때, 인접한 두 정점에 다른 색을 칠할 수 있다면 이 그래프는 이분 그래프이고, 반대로 인접한 두 정점이 같은 색을 가지면

이 그래프는 이분 그래프가 아니게 된다.

 

우선, 정점과 간선의 개수를 입력 받은 후, 간선의 개수대로 인접한 두 정점의 번호 u,v가 주어진다.

 

 

 	    int V = Integer.parseInt(st.nextToken()); // 정점의 수
            int E = Integer.parseInt(st.nextToken()); // 간선의 수
            
            // 그래프 초기화
            graph = new ArrayList<>();
            colors = new int[V + 1]; // 색칠 배열 (0: 미방문, 1: 빨강, -1: 파랑)
            
            for (int i = 0; i <= V; i++) {
                graph.add(new ArrayList<>());
            }
            
            // 간선 입력
            for (int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                graph.get(u).add(v);
                graph.get(v).add(u);
            }

 

여기서 colors 배열은 방문 여부를 의미하며, 아직 방문되지 않았다면 0, 빨강이면 1, 파랑이면 -1로 지정한다.

그래프는 ArrayList 배열을 사용하여 동적배열을 구현한다.

 

본격적인 BFS 구현은 이전에 계속해서 구현한 방식과 동일하다.

 

static boolean bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        colors[start] = 1; // 시작점을 빨간색으로 칠함
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            
            for (int neighbor : graph.get(current)) {
                if (colors[neighbor] == 0) { // 아직 방문하지 않았다면
                    colors[neighbor] = -colors[current]; // 현재 색과 반대 색으로 칠함
                    queue.add(neighbor);
                } else if (colors[neighbor] == colors[current]) { // 같은 색이면 이분 그래프 아님
                    return false;
                }
            }
        }
        
        return true;
    }

 

여기서 현재 방문한 정점(current)에 대해 인접한 정점(neighbor)들을 방문할 때,

colors[neighbor]가 0이라면 아직 미방문이므로 방문함을 colors[neighbor] = 현재 방문한 정점과 다른 색(-colors[current])으로 지정한다.

반면에, 인접한 정점이 현재 방문한 정점과 같은 색이면, 이 그래프는 이분 그래프가 아니므로 false를 반환하면 된다.

 

(full code)

 

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

public class Main {
    static List<List<Integer>> graph;
    static int[] colors;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 테스트 케이스의 수
        int K = Integer.parseInt(st.nextToken());

        while (K-- > 0) {
            // 각 테스트 케이스
            st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken()); // 정점의 수
            int E = Integer.parseInt(st.nextToken()); // 간선의 수
            
            // 그래프 초기화
            graph = new ArrayList<>();
            colors = new int[V + 1]; // 색칠 배열 (0: 미방문, 1: 빨강, -1: 파랑)
            
            for (int i = 0; i <= V; i++) {
                graph.add(new ArrayList<>());
            }
            
            // 간선 입력
            for (int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                graph.get(u).add(v);
                graph.get(v).add(u);
            }
            
            // 모든 정점에 대해 이분 그래프 여부 검사
            boolean isBipartite = true;
            for (int i = 1; i <= V; i++) {
                if (colors[i] == 0) { // 아직 방문하지 않은 정점
                    if (!bfs(i)) { // BFS로 이분 그래프 탐색
                        isBipartite = false;
                        break;
                    }
                }
            }
            
            // 결과 출력
            if (isBipartite) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }

    // BFS를 이용한 이분 그래프 판별 함수
    static boolean bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        colors[start] = 1; // 시작점을 빨간색으로 칠함
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            
            for (int neighbor : graph.get(current)) {
                if (colors[neighbor] == 0) { // 아직 방문하지 않았다면
                    colors[neighbor] = -colors[current]; // 현재 색과 반대 색으로 칠함
                    queue.add(neighbor);
                } else if (colors[neighbor] == colors[current]) { // 같은 색이면 이분 그래프 아님
                    return false;
                }
            }
        }
        
        return true;
    }
}