그래프) 백준 1707 (Java)

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

1707번: 이분 그래프

• 이분 그래프란, 일종의 Tree 형태로 표현할 수 있고, 그래프 간 Cycle이 존재하지 않아야 한다. 물론 Cycle이 존재하는 이분 그래프도 존재한다. (노드가 4개인 경우, 아래 사진 참고)

1. 문제 접근

• 그래프를 탐색하면서 각 노드 별로 집합을 정해주는 방식으로 진행한다. (DFS 사용)
  • 이 때 인접하는 노드와 집합이 같을 경우 이분 그래프가 형성되지 않는다.
• 그래프가 하나로 연결되지 않았을 때, 예외가 발생할 수 있으므로 각 노드별로 DFS 탐색을 해야 한다.
  • 이미 연결되어 있는 그래프들은 탐색을 다 했기 때문에 DFS 함수가 실행되더라도 바로 빠져 나온다.

2. 소스 코드

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

public class No1707 {
    static ArrayList<Integer>[] list;
    static boolean[] visited;
    static int[] nodeType; // 노드의 집합은 0과 1로 구분
    static boolean isBipartite;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        for (int i = 0; i < testCase; i++) {
            String[] input = br.readLine().split(" ");
            int V = Integer.parseInt(input[0]);
            int E = Integer.parseInt(input[1]);

            list = new ArrayList[V + 1];
            visited = new boolean[V + 1];
            nodeType = new int[V + 1];
            isBipartite = true;

            for (int j = 1; j <= V; j++) {
                list[j] = new ArrayList<Integer>();
            }
            for (int j = 0; j < E; j++) {
                input = br.readLine().split(" ");
                int start = Integer.parseInt(input[0]);
                int end = Integer.parseInt(input[1]);
                list[start].add(end);
                list[end].add(start);
            }

            for (int j = 1; j <= V; j++) {
                if (isBipartite) {
                    DFS(j);
                } else {
                    break;
                }
            }

            if (isBipartite) System.out.println("YES");
            else System.out.println("NO");
        }
    }

    private static void DFS(int start){
        visited[start] = true;
        for (int adj : list[start]) {
            if(!visited[adj]){
                nodeType[adj] = (nodeType[start] + 1) % 2;
                DFS(adj);
            } else if (nodeType[start] == nodeType[adj]) {
                isBipartite = false;
            }
        }
    }
}

3. 중요 부분

• ArrayList를 사용하여 인접 리스트를 구현하였고, 엣지에 방향이 없기 때문에 인접한 노드들 끼리는 서로 추가를 해야 한다.
  • foreach문을 사용하여 각 리스트별로 탐색이 가능하다.
• 한 줄에 입력받는 데이터가 많지 않은 경우 Stringtokenizer를 사용하기 보다는 String[] 타입의 input 변수와 split(" ")을 통해 공백 단위로 데이터를 저장하는 것을 권장한다. 위 문제처럼 엣지별로 입력받는 노드가 두 개인 경우엔 split 함수를 사용하여 input 값을 나누는 것이 코드도 간결하고 편하다.
• nodeType의 경우 node 별 집합을 나누는 배열이다. 각 노드를 방문하면서 방문했는지 체크하는 배열(visited)과 함께 각 노드 별로 집합을 표시하기 위한 배열, nodeType 배열이 필요하다. 이처럼 그래프 탐색에서 각 노드별로 확인해야 하는 요소가 많을 경우 여러 개의 배열을 사용할 수 있다.
  • 노드의 집합은 A/B일 수도 있고, 0과 1로 나눌 수도 있다. 0과 1로 하는 것이 코드 작성에는 편할 것이다. 위처럼 각 노드를 방문하면서 현재 노드가 0이면 다음 인접 노드는 1이 되어야 하고, 반대로 1이면 인접 노드는 0이 되어야 한다. 현재 nodeType 값에 1을 더하되, 1인 상태에서 1을 더하면 2가 된다. 이를 다시 0으로 바꿔야 하기 때문에 2로 나누는 모듈려 연산 한다. 그러면 2를 2로 나눈 나머지인 0이 되고, 다시 0에서 1로 변할 수 있다. 이처럼 모듈러 연산을 사용하여 반복되는 숫자 타입을 지정하는 것이 가능하다.

 

소스코드 출처 :

https://www.youtube.com/watch?v=mDSQfb5Rqc4