[BOJ] 1707 - 이분 그래프 판별 (Java)

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

 

문제 분석

이 문제는 노드와 간선으로 이루어진 그래프를 입력 받아 해당 그래프가 이분 그래프인지 판별을 하여 이분 그래프가 되면 YES를 아니면 NO를 출력하는 문제이다. 우선 주어진 데이터를 보면 간선에 방향이 없기 때문에 무방향 그래프로 만들어야 하는 것을 알 수 있다. 또한 이분 그래프 판별을 위한 DFS를 하기 위해서 필요한 방문 여부 배열, 이분 그래프 판별 용 변수 등을 만들어야 한다. 

그리고 여기서 중요한게 이분 그래프를 정확히 이해하는 것이다. 이분 그래프에 대한 자세한 내용은 검색을 하는 것으로 대체하고 간단히 설명을 하면 하나의 간선마다 연결된 두개의 노드가 서로 다른 집합에 속하고 이 조건을 모든 간선이 통과하면 이분 그래프로 판별하는 것이다. 이 조건만 보면 간단해 보이는 데 하나의 함정이 더 있다. 바로 주어진 그래프가 떨어져 있어도 홀수개의 노드로 이루어진 사이클만 만들어 지지 않으면 이분 그래프로 판별해야 한다는 점이다.

이 경우를 자세하게 말하자면 노드가 총 5개이고 간선은 1-2, 3-4, 4-5, 5-3 로 이루어진 그래프가 있을때를 보면 1,2 와 3,4,5는 서로 이어지지 않았다. 하지만 떨어져있다는 것은 이분 그래프 판별에 전혀 영향을 주지 않는다. 이분 그래프 판별 조건은 오로지 하나의 간선에 연결된 두개의 노드가 다른 집합에 속해 있어야 한다는 것이기 때문이다. 하지만 위 그래프는 3,4,5 가 홀수개의 노드로 이루어진 사이클을 형성하기 때문에 이분 그래프가 되지 못한다. 

반면 6개의 노드가 있고 간선은 1-2, 3-4, 4-5, 5-6, 6-3으로 이루어진 그래프는 1-2는 이분그래프이고 나머지 노드들도 사이클을 이루긴 하지만 짝수개의 노드로 이루어진 사이클이기 때문에 이분 그래프로 판별이 가능하기 때문에 전체적으로 보면 이분 그래프가 되는 것이다.

 

코드

이제 코드를 보

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static boolean[] visited;
    static String[] set;
    static boolean result=true;
    static ArrayList<Integer>[] graph;

    public static void main(String[] args) throws IOException{
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(bf.readLine());

        int k=Integer.parseInt(st.nextToken());
        for(int q=0;q<k;q++){
            st=new StringTokenizer(bf.readLine());
            int v=Integer.parseInt(st.nextToken());
            int e=Integer.parseInt(st.nextToken());
            //init
            visited=new boolean[v+1];
            set=new String[v+1];
            result=true;
            graph=new ArrayList[v+1];
            for(int i=0;i<=v;i++){
                graph[i]=new ArrayList<>();
            }
            //graph 만들기
            for(int i=1;i<=e;i++){
                st=new StringTokenizer(bf.readLine());
                int S=Integer.parseInt(st.nextToken());
                int E=Integer.parseInt(st.nextToken());

                graph[S].add(E);
                graph[E].add(S);
            }

            for(int j=1;j<=v;j++){
                if(!visited[j]){
                    set[j]="A";
                    DFS(j);
                }
            }
//            for(int j=1;j<=v;j++){
//                if(result){
//                    set[j]="A";
//                    DFS(j);
//                }else break;
//            }
            if(result){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }
        }
    }
    private static void DFS(int node){
        visited[node]=true;
        for(int next : graph[node]){
            if(!visited[next]){
                set[next]=set[node].equals("A") ? "B" : "A";
                DFS(next);
            }else{
                if(set[next].equals(set[node])){
                    result=false;
                }
            }
        }
    }
}

 

위 코드를 보면 DFS를 이용해서 이분 그래프를 판별하는 것을 볼 수 있다. 그래프에 대한 데이터를 입력 받고 그래프를 만들어서 해당 그래프로 DFS를 하기전 처음 시작하는 노드는 "A"로 초기화를 하고 간선을 따라서 다음 노드는 그 반대로 설정을 해서 간선을 따라 갔는데 도착 노드를 이미 방문한 적이 있고 도착 노드의 값과 출발 노드의 값이 같으면 이분 그래프 형성 실패로 판단하고 result를 false로 설정한다.

이 문제를 풀면서 시간을 많이 잡아먹은 부분이 DFS 실행전 조건 설정 부분이다. 위에서 주석 처리를 한 부분인데 원래는 주어진 그래프가 나눠져 있더라도 한 부분의 그래프에서 이분 그래프를 형성하지 못하면 모든 노드에 대한 DFS를 하지 않고 바로 결과를 출력하는 방식이였지만 계속해서 6%에서 틀렸다고 나와서 모든 노드에 대해 DFS를 하는 방식으로 바꾸고 나서 문제를 해결했다. 

사실 아직까지 정확하게 문제 이해를 하지 못한거 같다. DFS 실행 반복의 조건을 조금만 바꾸어도 통과/불통과 가 나뉘어 져서 왜 그런지는 더 공부를 해봐야 할거같다.

//불통
for(int j=1;j<=v;j++){
	if(result){
		set[j]="A";
		DFS(j);
	}
}
//통과
for(int j=1;j<=v;j++){
	if(!visited[j]){
		set[j]="A";
		DFS(j);
		if(!result){
			break;
		}
	}
}