[백준] 1707번 : 이분 그래프

이분 그래프

---

풀이 방법

이분 그래프를 구현하는 문제였다.
우선 이분 그래프가 무엇인지 이해해야 한다.

이분 그래프

참고 블로그 (이해를 위한 설명과 사진 참조)
https://www.ksakosmos.com/post/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%9D%B4%EB%A1%A0-%EB%A7%9B%EB%B3%B4%EA%B8%B0-%EC%9D%B4%EB%B6%84-%EA%B7%B8%EB%9E%98%ED%94%84

이 처럼 2 집합으로 나눠서 각 집합에 속한 정점끼리는 인접되지 않는, 즉 간선이 직접 연결되서는 안된다.

구현

참고 블로그
https://velog.io/@zayson/%EB%B0%B1%EC%A4%80-Java-1707%EB%B2%88-%EC%9D%B4%EB%B6%84-%EA%B7%B8%EB%9E%98%ED%94%84

1. 색칠되지 않은 모든 정점에 대해 BFS를 진행한다.
2. BFS의 시작 정점을 임의의 색상으로 색칠한다.
3. 연결된 정점을 다른 색상으로 색칠한다.
4. 연결된 정점이 서로 동일한 색상을 가지는 경우 이분 그래프가 아니므로 false 반환한다.
5. 모든 정점이 각 독립된 그룹을 구성하면 이분 그래프이다.

알게된 점

• ArrayList와 LinkedList의 차이

• 출처 : http://changpd.blogspot.com/2014/08/arraylist-linkedlist-java.html

정리하자면

삽입과 삭제가 많다면 ArrayList는 비효율적이다.

LinkedList는 순차적 접근이기 때문에 검색의 속도가 느리다.

그래서 LinkedList로 구현해버리면 시간초과 오류가 났다... 이런 사소한 점을 꼭 기억하자.!!

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static List<List<Integer>> graph;
    static int[] colors;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int k = Integer.parseInt(br.readLine());
        for(int i=0;i<k;i++){
            st = new StringTokenizer(br.readLine()," ");
            int v = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            //초기화
            colors = new int[v+1];
            graph = new ArrayList<>();
            for(int j=0;j<=v;j++){
                graph.add(new ArrayList<>());
            }

            //그래프 설정
            for(int j=0;j<e;j++){
                st = new StringTokenizer(br.readLine()," ");
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());

                graph.get(from).add(to);
                graph.get(to).add(from);
            }

            boolean check = false;
            //모든 정점을 방문
            for(int vertex=1;vertex<=v;vertex++){
                if(colors[vertex] == 0){
                    check = BFS(vertex, 1);
                }
                if(!check){
                    break;
                }
            }
            if(check) System.out.println("YES");
            else System.out.println("NO");
        }
    }

    private static boolean BFS(int start, int color) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        //시작 정점 색칠
        colors[start] = color;

        while(!queue.isEmpty()) {
            int cur = queue.remove();
            for (int next : graph.get(cur)) {
                //인접 정점 색이 동일하면 이분 그래프가 아님
                if (colors[cur] == colors[next]) {
                    return false;
                }
                //현재 정점의 반대 색깔로 색칠
                if(colors[next] == 0){
                    colors[next] = colors[cur] * -1;
                    queue.add(next);
                }
            }
        }
        return true;
    }
}