[백준 1707번] 이분 그래프 - JAVA

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

1707번: 이분 그래프

풀이

사용한 알고리즘: BFS

 

풀이전략

문제를 풀기 앞서 이분 그래프가 어떤 구조인지 알고 있어야 문제 풀이가 가능하다.

위와 같은 그래프가 있을 때, 인접한 노드끼리 서로 다른 색을 지니는 그래프를 이분 그래프라고 한다.

 

노드끼리 모두 연결되어 있지 않아도, 서로 인접한 노드끼리만 다른 색으로 구분될 수 있어도 이분그래프다.

 

이런 이분 그래프의 성질을 이용하여 BFS를 사용하면 문제를 풀 수 있다.

 

1. 각 노드마다 갈 수 있는 노드를 이차원 어레이 리스트 형식으로 그래프를 그린다.

2. 시작 노드를 선택하고 Queue에 노드 번호를 저장한 후,

   해당 노드의 방문 여부를 저장한 변수의 값을 1로 변경한다.

  (0= 아직 방문 안함,  1= 방문함,   -1=방문함 // 1과 -1은 인접한 노드 간 다른 색으로 구분할 수 있도록

   2가지로 구분하였다.)

3. 큐에 있는 노드 번호를 pop한다.

4. pop한 노드와 인접한 노드들 중 아직 방문하지 않은 노드를 방문한다.

5. 방문하지 않은 노드의 방문 변수 값을 (현재 노드의 방문 변수 값) X -1로 저장하고

    노드 번호를 큐에 저장한다.

6. 3~5번을 반복하는 중 현재 노드와 인전한 노드의 방문 변수 값이 일치하면 "No"를 출력,

    반복 종료까지 일치하는 값이 없으면 "YES"를 출력한다. 

 

제출코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static ArrayList<ArrayList<Integer>> graph;
    static int color[];

    static boolean bfs(int x){
        Queue<Integer> q = new LinkedList<>();
        color[x]=1;
        q.offer(x);

        while(!q.isEmpty()){
            int val=q.poll();
            for(int i=0;i<graph.get(val).size();++i){
                if(color[val]==color[graph.get(val).get(i)]) return false;

                if(color[graph.get(val).get(i)]==0){
                    color[graph.get(val).get(i)]=color[val]*-1;
                    q.offer(graph.get(val).get(i));
                }
            }
        }
        return true;
    }
    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

            graph=new ArrayList<>();
            for(int j=0;j<V+1;++j){
                graph.add(new ArrayList<>());
            }
            color=new int[V+1];

            for(int j=0;j<E;++j){
                st=new StringTokenizer(br.readLine());
                int a=Integer.parseInt(st.nextToken());
                int b=Integer.parseInt(st.nextToken());
                graph.get(a).add(b);
                graph.get(b).add(a);
            }

            boolean check=true;
            for(int j=1;j<V+1;++j) {
                if (color[j] == 0) {
                    check = bfs(j);
                    if(check==false) {
                        break;
                    }
                }
            }
            if(check==true) System.out.println("YES");
            else System.out.println("NO");
            graph.clear();
        }
    }
}