백준 1707번 : 이분 그래프 java

이 문제는 이분 그래프인지 아닌지를 확인하는 문제입니다.

우선 이분 그래프가 무엇인지에 대해서 설명드리겠습니다.

이분 그래프란 위의 그림과 같이 연결된 두 정점의 색깔을 다르게 칠할 수 있는 그래프입니다.

위의 그림과 같이 빨간 간선이 추가되어 연결된 두 노드의 색깔이 같다면 이는 이분 그래프라 말할 수 없습니다.

그래프가 이분 그래프인지 확인하는 방법은 dfs를 이용하는 방법과 bfs를 이용하는 방법이 있습니다.

저는 이 중에서 dfs를 이용하였습니다.

하나의 정점을 선택한 후 dfs를 이용하여 이동할 때 이동한 간선이 이전의 간선과 다른 타입으로 만들 수 있는지를
확인하면서 진행하였습니다.

이미 방문한 정점이라도 다른 타입인지를 확인하게 만들었습니다.

코드를 보여드리도록 하겠습니다.

---

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

public class Main {
    static List<List<Integer>> l;
    static boolean[] visited;
    static int[] type;
    static boolean flag;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();

        int K = Integer.parseInt(br.readLine());

        while (K-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());

            visited = new boolean[V+1];
            type = new int[V+1];

            l = new ArrayList<>();
            for(int i = 0; i<=V; i++)
                l.add(new ArrayList<>());

            //그래프의 간선을 입력
            for(int i = 0; i<E; i++){
                st = new StringTokenizer(br.readLine());

                int A = Integer.parseInt(st.nextToken());
                int B = Integer.parseInt(st.nextToken());

                l.get(A).add(B);
                l.get(B).add(A);
            }

            flag = true;
            //연결 그래프가 아닐 수 있으므로 모든 정점에 대해서 dfs
            for(int i = 1; i<=V; i++)
                if(!visited[i])
                    dfs(i, 2);

            if(flag)
                sb.append("YES").append("\n");
            else
                sb.append("NO").append("\n");
        }

        System.out.print(sb);
    }

    static void dfs(int vertex, int exType){
        visited[vertex] = true;
        type[vertex] = exType == 1 ? 2 : 1;

        for(int i = 0; i<l.get(vertex).size(); i++){
            int nextVertex = l.get(vertex).get(i);

            if(visited[nextVertex]) {
                if (type[vertex] == type[nextVertex])
                    flag = false;
            }

            else
                dfs(nextVertex, type[vertex]);
        }
    }
}

위와 같이 dfs를 사용할 수도 있고 bfs를 이용하여 주변의 노드들을 다른 색으로 칠할 수 있는지 확인하면서 문제를 해결할 수도 있습니다.