[Algorithm] 99클럽 코테 스터디 9일차 TIL | 백준_이분 그래프(1707번)

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

---

이분 그래프는 정점을 두 그룹으로 나눌 수 있어야 하는데,

 

ArrayList<Integer> [] 배열을 사용하여 인접 리스트를 생성하고

ArrayList<Integer>[] graph = new ArrayList[V];
for(int j = 0; j < V; j++){
    graph[j] = new ArrayList<>();
}
for(int j = 0; j < E; j++){
    st = new StringTokenizer(br.readLine());
    int node1 = Integer.parseInt(st.nextToken()) - 1;
    int node2 = Integer.parseInt(st.nextToken()) - 1;

    graph[node1].add(node2);
    graph[node2].add(node1);
}

 

colors가 0이면 미방문 정점

처음 방문하게 되는 정점을 1로 두고

그 정점과 인접한 정점들은 -1로 설정한다.

 

만약 인접한 정점과 현재 정점이 같다면? 이분 그래프가 아니다!

public static boolean bfs(int n, ArrayList<Integer>[] graph, int[] colors){
    Queue<Integer> queue = new LinkedList<>();
    queue.add(n);
    colors[n] = 1;

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

 

인접 정점이 다음과 같을 때를 대비하여

1--2

3--4

5--4

3--5

for(int j = 0; j < V; j++){
    if(colors[j] == 0){
        if(!bfs(j, graph, colors)){
            result = false;
            break;
        }
    }
}

위 코드가 추가되어야 한다.

 

위 코드가 없으면

1--2만 돌고 검사를 끝내기 때문이다..

 

 

전체 코드

import java.util.*;
import java.io.*;
class Main{
    static StringBuilder answer = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i = 0; i < K; i++){
            st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            //ArrayList를 요소로 갖는 배열
            ArrayList<Integer>[] graph = new ArrayList[V];
            for(int j = 0; j < V; j++){
                graph[j] = new ArrayList<>();
            }
            for(int j = 0; j < E; j++){
                st = new StringTokenizer(br.readLine());
                int node1 = Integer.parseInt(st.nextToken()) - 1;
                int node2 = Integer.parseInt(st.nextToken()) - 1;

                graph[node1].add(node2);
                graph[node2].add(node1);
            }
            int[] colors = new int[V];
            boolean result = true;
            for(int j = 0; j < V; j++){
                if(colors[j] == 0){
                    if(!bfs(j, graph, colors)){
                        result = false;
                        break;
                    }
                }
            }
            answer.append(result ? "YES" : "NO").append("\n");
        }
        System.out.println(answer);
    }
    public static boolean bfs(int n, ArrayList<Integer>[] graph, int[] colors){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(n);
        colors[n] = 1;

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