[코딩테스트] 백준 1707 자바

백준 1707

백준 1707 문제

해당 문제는 인접한 노드가 같은 집합이면 안되는 이분 그래프인지 확인하는 문제이다.

주어지는 그래프가 모두 연결되어있다는 조건이 없기 때문에 모든 노드에 대해 DFS을 통해 인접한 모든 노드를 확인해야 한다.

DFS를 수행하다가 방문했던 노드를 만나게 되면 만나게 된 두 인접 노드의 집합이 같으면 이분 그래프가 아니기 때문에 바로 NO를 출력하면 되고, DFS가 끝까지 돌 때까지 인접한 노드들의 집합이 모두 다르면 이분 그래프이기 때문에 YES를 출력하면 된다.

import java.io.*;
import java.util.*;

public class Boj1707 {

    static ArrayList<Integer>[] list;
    static int[] check;
    static boolean[] visited;
    static boolean isEven;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());

        for (int t = 0; t < testCase; t++) { // 주어진 테스트케이스만큼 반복
            String[] s = br.readLine().split(" ");
            int v = Integer.parseInt(s[0]); // 노드의 개수
            int e = Integer.parseInt(s[1]); // 에지의 개수
            list = new ArrayList[v + 1]; // 인접 리스트 생성
            visited = new boolean[v + 1]; // 방문 배열 생성
            check = new int[v + 1]; // 집합 확인 배열 생성
            isEven = true; // 이분 그래프 확인 변수 생성

            for (int i = 1; i <= v; i++) { // 인접 리스트 초기화
                list[i] = new ArrayList<Integer>();
            }

            // 에지 데이터 저장
            for (int i = 0; i < e; i++) {
                s = br.readLine().split(" ");
                int start = Integer.parseInt(s[0]); // 시작 노드
                int end = Integer.parseInt(s[1]); // 도착 노드
                // 방향성이 없기 때문에 양쪽에 추가
                list[start].add(end);
                list[end].add(start);
            }

            // 모든 노드에서 DFS 실행
            for (int i = 1; i <= v; i++) {
                if (isEven) { // 이분 그래프이면 dfs 실행
                    dfs(i);
                } else { // 이분 그래프가 아니면 반복 종료
                    break;
                }
            }

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

    private static void dfs(int start) {
        visited[start] = true; // 방문 기록
        for (int i : list[start]) { // 인접 리스트로 받아서 start에서 연결된 모든 노드를 탐색하게 된다.
            if (!visited[i]) { // 방문하지 않은 노드면
                // 바로 직전에 있는 노드와 다른 집합으로 분류를 해주는 것이 필요
                check[i] = (check[start] + 1) % 2; // 0과 1로 집합 표시
                dfs(i); // 재귀 호출
            } else if (check[start] == check[i]) { // 인접 노드가 같은 집합이면
                isEven = false; // 이분 그래프가 아님
            }
        }
    }
}

풀이

1. 인접 리스트와 방문 배열, 집합 배열, 이분 그래프 확인 변수를 스태틱으로 선언한다.
2. 테스트케이스의 갯수를 testCase 변수로 입력 받는다.
3. testCase만큼 반복한다.
4. 노드의 갯수를 v, 에지의 개수를 e로 입력 받는다.
5. 0 인덱스는 사용하지 않을 것이기 때문에 인접 리스트, 방문 배열, 집합 배열 모두 v+1로 생성한다.
6. 이분 그래프 확인 변수 isEven은 true로 초기화한다.
7. 인접 리스트의 길이만큼 반복하면서 new ArrayList<Integer>()로 초기화 해준다.
8. 해당 에지들은 방향성이 없기 때문에 e만큼 반복하면서 입력된 시작 노드 start와 도착 노드 end 각각의 인접 리스트에 서로 인접 노드로 추가해준다.
9. 해당 그래프는 모두 연결되어있다는 조건이 없기 때문에 하나의 그래프가 아닐 수도 있다. 따라서 모든 노드에 대해서 DFS를 실행시켜 확인해야 된다. 1부터 v까지 반복하며 dfs(i)를 호출하고 isEven이 false이면 이분 그래프가 아니기 때문에 바로 반복을 중단하도록 한다.
10. dfs() 메서드는 들어온 노드의 방문을 기록하고 인접 노드들에 (check[start] + 1) % 2 MOD 연산을 통해 0과 1로 집합을 입력해주고 dfs()를 재귀 호출하며 DFS를 실행한다.
11. DFS를 실행하다가 방문했던 인접 노드를 방문하게 될 때, 두 인접한 노드들의 집합을 확인한다.
12. 두 인접한 노드의 집합이 같다면 이분 그래프가 아니기 때문에 isEven를 false로 변경한다.