백준 - 1707 이분그래프 (JAVA)

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

1707번: 이분 그래프

 

문제설명

 

이분 그래프 문제이다. 이분그래프 문제는 BFS로 구현하는 것이 정석이다.

 

알고리즘

 

1. 삽입 삭제가 빈번하면 LinkedlList 조회가 많으면 ArrayList를 사용하는데 BFS 임으로 ArrayList가

더 빠른 시간내에 해결 할 수 있다.

 

2. ArrayList를 통해 그래프를 만들고 처음 시작 정점의 값을 -1 로 초기화한다.

 

3. BFS를 이용하여 하나의 정점에 연결되어 있는 정점들을 -1 * -1로 반대의 값을 넣는다.

 

4. BFS 도중 연결되어 있는 정점과 같은 값이면 false 아무 문제없이 완료하면 true를 반환한다.

 

주의사항

 

1. 연결이 안된 동 떨어진 정점이 있는 TK가 있으니 모든 정점을 살펴봐야한다.

 

구현

 

public static void main(String args[]) throws Exception
{
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(in.readLine().trim());
    for (int test_case = 1; test_case <= T; test_case++) 
    {
        StringTokenizer s = new StringTokenizer(in.readLine()," ");
        V = Integer.parseInt(s.nextToken());
        E = Integer.parseInt(s.nextToken());
        check = new int[V+1]; //1부터 쓸것이기 때문에 check 크기 1크게
        adj = new ArrayList[V+1]; // 마찬가지로 인접리스트 크기 1크게 -> 정점 수가 20000개라서 2차배열로 돌리려면 메모리 소모가 심하다.
        for (int i = 1; i <= V; i++) { //각 인접 배열마다 리스트 생성
            adj[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < E; i++) {
        s = new StringTokenizer(in.readLine()," ");
        int a =Integer.parseInt(s.nextToken());
        int b =Integer.parseInt(s.nextToken());
        adj[a].add(b); //양방향 연결
        adj[b].add(a);
        }

        boolean flag = false; 

        for (int i = 1; i <= V; i++) 
        {
            if(check[i] == 0) //모든 정점이 안 이어질 수도 있기 때문에 검사
            flag = BFS(i); //bfs
            if(!flag)
                break;
        }

        if(flag)
            System.out.println("YES");
        else
            System.out.println("NO");
    }
}
private static boolean BFS(int start) {
    LinkedList<Integer> queue = new LinkedList<Integer>();
    queue.offer(start); 
    check[start] = -1; //시작을 -1컬러로 시작
    while(!queue.isEmpty())
    {
        int v = queue.poll();
        for (int i = 0; i < adj[v].size(); i++) {
            int ne = adj[v].get(i);
            if(check[ne] == check[v])
                return false;
            else if(check[ne] == 0)
            {
                check[ne] = check[v]*-1;
                queue.offer(ne);
            }
        }
    }
    return true; //아무일도 없으면 true
}

 ```