📘 백준 문제 풀이: 이분 그래프

백준 문제 "이분 그래프"를 풀어보겠습니다. 이 문제는 DFS나 BFS 알고리즘을 활용하여 주어진 그래프가 이분 그래프인지 판별하는 문제입니다.

문제 설명

📝 문제 조건

그래프
- 입력으로 주어지는 그래프는 방향이 없는 무방향 그래프
- 그래프가 연결되지 않을수도 있음
이분그래프
- 그래프의 정점을 두 그룹으로 나눌 수 있고, 같은 그룹에 속한 정점들간에 간선이 없을때 이분그래프
- 간선이 없는경우도 두 그룹으로 나눌 수 있기 때문에 이분그래프이다.
  🔑 문제 풀이 아이디어
각 정점을 두가지 색으로 색칠
- 두 그룹으로 나누기
이분 그래프 판별 방법 : 인접한 노드들이 같은 그룹이면 이분 그래프가 아니다.
탐색하는 방식은 DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)을 사용해 구현이 가능한다.
- 그래프를 탐색하며 각 정점에 대해 다른색을 할당
- 탐색중 인접한 정점이 같은색으로 칠해져야하는경우, 이분 그래프가 아님

코드 구현

BFS를 사용한 구현

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

public class Main {
    static List<Integer>[] graph;
    static int[] colors;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int K = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

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

            graph = new ArrayList[V + 1];
            colors = new int[V +1];
            for (int j = 1; j <= V; j++) {
                graph[j] = new ArrayList<>();
            }

            for (int j = 0; j < E; j++) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                graph[u].add(v);
                graph[v].add(u);
            }
            boolean isBipartite = true;
            for (int j = 1; j <= V; j++) {
                if(colors[j] == 0){
                    if(!bfs(j)){
                        isBipartite = false;
                        break;
                    }
                }
            }
            sb.append(isBipartite ? "YES" : "NO").append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    public static boolean bfs(int start){
        Queue<Integer> q = new LinkedList<>();
        colors[start] = 1;
        q.add(start);

        while(!q.isEmpty()){
            int current = q.poll();
            for (int n : graph[current]) {
               if(colors[n] == 0){
                   colors[n] = -colors[current];
                   q.add(n);
               }else if (colors[n] == colors[current]){
                   return false;
               }
            }
        }
        return true;
    }
}

코드 설명

1️⃣ 입력 처리

•    BufferedReader와 BufferedWriter를 사용해 입력과 출력을 빠르게 처리합니다.
•    BufferedReader는 대량의 입력 데이터를 처리할 때 유리하며, 입력 데이터를 문자열로 읽어옵니다.
•    BufferedWriter는 출력 데이터를 모아 한 번에 출력하므로 성능을 높입니다.
•    StringTokenizer를 사용해 한 줄에 입력된 정점과 간선 정보를 파싱합니다.

2️⃣ 입력 처리

•    인접 리스트(List<Integer>[] graph)를 사용해 그래프를 저장합니다.
•    각 정점에 연결된 인접 정점을 리스트로 관리합니다.
•    메모리 사용량이 적고, 탐색에 효율적입니다.

3️⃣ BFS를 통한 이분 그래프 판별

•    BFS를 사용해 정점을 순회하며 색칠을 진행합니다.
•    colors 배열은 각 정점의 색을 저장합니다.
•     1 : 색 1.
•    -1: 색 -1.
•     0 : 아직 방문하지 않은 정점.
•    현재 정점과 연결된 정점은 항상 다른 색으로 칠합니다.
•    Queue를 사용해 너비 우선 탐색을 수행합니다.
•    현재 정점에서 시작해 연결된 정점을 큐에 추가합니다.
•    이미 색칠된 정점의 색이 현재 정점과 같다면 이분 그래프가 아닙니다.

4️⃣ 여러 테스트 케이스 처리

•    테스트 케이스 수( K )만큼 반복하며 그래프를 초기화하고 탐색을 수행합니다.
•    각 테스트 케이스의 결과를 StringBuilder에 저장한 뒤, 마지막에 한꺼번에 출력합니다.

주요 로직

BFS 함수 동작 과정

시작 정점을 색 1로 칠하고 큐에 추가합니다.
큐에서 정점을 하나씩 꺼내며:
• 인접 정점이 방문되지 않았다면 현재 정점의 반대 색으로 칠합니다.
• 이미 방문된 정점이 같은 색이라면 이분 그래프가 아님을 반환합니다.
모든 정점 탐색이 완료되면 이분 그래프 조건을 만족한 것으로 판단합니다.

시간 복잡도

•    그래프 탐색:
•    BFS는 모든 정점과 간선을 탐색합니다.
•    시간 복잡도:  O(V + E)  ( V : 정점 수,  E : 간선 수)
•    입출력:
•     O(K)  (테스트 케이스 수)

마무리

로직자체는 어렵지 않았지만 문제 자체를 이해하기 쉽지 않았던 문제였던것 같다. 이분 그래프에 대한 개념을 이해하는데에 가장 많은 시간을 썻고, 시간을 줄이기 위해서는 비슷한 문제를 많이 풀어서 문제 이해도를 높이는게 좋다고 생각이 들었다.

99클럽 코테 스터디 9일차 TIL - 백준 1707 이분 그래프 | BFS - java