알고리즘 풀이 - 백준 1707(이분 그래프, 그래프(DFS, BFS))

관련글

 

그래프 관련 포스팅은 여기를 참조
이분 그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

그래프가 이분 그래프인지 여부를 판별하는 문제

 

 

2. 풀이

 

이분 그래프는 아래와 같이 2 그룹으로 나누었을 때, 같은 그룹은 서로 인접하지 않아야 한다.

 

 

위의 그림과 같이 빨간 그룹과 파란 그룹이 있는데 같은 그룹은 인접하여 연결되지 않았다. 이런 경우 이분 그래프라고 할 수 있다.

 

이를 구하는 방법은 그래프를 탐색하며 인접한 정점들이 같은 속성(보통 색깔로 표현)을 가지지 않는지를 검사하면 된다.

 

기본적으로 탐색을 수행하면서 현재 탐색 중인 정점의 색상을 지정하고, 그것과 인접한 모든 정점을 탐색하되 인접한 정점 중 같은 색상으로 지정된 정점이 있다면 이분 그래프가 아님을 알 수 있다.

참고로, 아예 어떠한 정점과도 연결되지 않은 독립적인 정점만으로 구성된 경우에도 이분 그래프라고 할 수 있기 때문에 그것 또한 고려하여 코드를 작성 해야 한다.(모든 정점에서 탐색 시작 - 반복문 구현)

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

① BFS로 해결하기

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

public class Main{
    static int v;
    static int e;
    static ArrayList<Integer>[] graph;
    static int[] color;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        // 테스트 케이스 수행
        while(t-- > 0){
            st = new StringTokenizer(br.readLine());
            v = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());

            // 그래프 인접 리스트 및 색상 정보 초기화
            graph = new ArrayList[v+1];
            color = new int[v+1];
            for(int i=1; i <= v; i++){
                graph[i] = new ArrayList<>();
            }

            // 주어진 간선 정보 연결
            for(int i=0; i < e; i++){
                st = new StringTokenizer(br.readLine());
                int v1 = Integer.parseInt(st.nextToken());
                int v2 = Integer.parseInt(st.nextToken());

                graph[v1].add(v2);
                graph[v2].add(v1);
            }

            // bfs 탐색을 통해 이분 그래프인지 확인
            boolean isBipartite = true;
            for(int i=1; i <= v; i++){
                // 이미 방문 완료된 정점이면 넘어간다.
                if(color[i] != 0) continue;
                isBipartite = bfs(i);

                // 중간에 아님이 판명된 경우 반복문을 멈춘다.
                if(!isBipartite) break;
            }


            // 이분 그래프 여부에 따라 출력
            bw.write(isBipartite ? "YES" : "NO");
            bw.write("\n");
        }

        bw.flush();
        br.close();
    }

    private static boolean bfs(int start){
        // 전달된 번호부터 시작하여 BFS 탐색 수행
        color[start] = 1;

        Queue<Integer> q = new LinkedList<>();
        q.offer(start);

        while(!q.isEmpty()){
            // 현재 위치에서 시작
            int c = q.poll();

            for(int i : graph[c]){
                // 아직 방문되지 않은 정점이라면 큐에 넣고 현재 색상과 다른 색상으로 저장
                if(color[i] == 0){
                    q.offer(i);
                    color[i] = color[c] * -1;
                    // 이미 방문된 정점인 경우
                } else {
                    // 현재 정점의 색상과 같다면 이분 그래프가 아님
                    if(color[i] == color[c]){
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

 

② DFS로 해결하기

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

public class Main{
    static int v;
    static int e;
    static ArrayList<Integer>[] graph;
    static int[] color;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        // 테스트 케이스 수행
        while(t-- > 0){
            st = new StringTokenizer(br.readLine());
            v = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());

            // 그래프 인접 리스트 및 색상 정보 초기화
            graph = new ArrayList[v+1];
            color = new int[v+1];
            for(int i=1; i <= v; i++){
                graph[i] = new ArrayList<>();
            }

            // 주어진 간선 정보 연결
            for(int i=0; i < e; i++){
                st = new StringTokenizer(br.readLine());
                int v1 = Integer.parseInt(st.nextToken());
                int v2 = Integer.parseInt(st.nextToken());

                graph[v1].add(v2);
                graph[v2].add(v1);
            }

            // dfs 탐색을 통해 이분 그래프인지 확인
            boolean isBipartite = true;
            for(int i=1; i <= v; i++){
                // 이미 방문 완료된 정점이면 넘어간다.
                if(color[i] != 0) continue;
                isBipartite = dfs(i, 1);

                // 중간에 아님이 판명된 경우 반복문을 멈춘다.
                if(!isBipartite) break;
            }

            // 이분 그래프 여부에 따라 출력
            bw.write(isBipartite ? "YES" : "NO");
            bw.write("\n");
        }

        bw.flush();
        br.close();
    }

    private static boolean dfs(int curr, int col){
        color[curr] = col;
        int nextCol = col * -1;

        boolean result = true;
        for(int i : graph[curr]){

            // 아직 방문되지 않은 경우
            if(color[i] == 0){
                result = dfs(i, nextCol);
            } else {
                if(color[i] == color[curr]) return false;
            }
            
            // false를 반환 받았다면 바로 되돌아간다.
            if(!result) return result;
        }
        return true;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.