[Java] 백준 16168 퍼레이드

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

난이도

골드 4

문제

종우는 18학번을 대표하여 중앙대학교 개교 100주년 기념 퍼레이드의 경로 선정 위원으로 선정되었다. 퍼레이드의 경로는 일정한 지점들과 두 지점을 연결하는 연결 구간으로 이루어져 있다. 종우는 모든 지점을 지나면서 모든 연결 구간들을 지나고 싶어한다.

하지만 같은 연결 구간을 두 번 이상 지날 경우 그 구간의 주민들이 민원을 제기하게 된다. 단, 같은 지점은 두 번 이상 지나도 된다.

민원을 받지 않으면서 모든 구간을 지나도록 퍼레이드를 만들고 싶은 종우를 위한 프로그램을 작성해보도록 하자.

입력

첫 번째 줄에 지점의 개수 V, 연결 구간의 개수 E가 주어진다. (1 ≤ V ≤ E ≤ 3000) 이후 E개의 줄에 걸쳐 각 연결 구간이 연결하는 두 지점의 번호 Va, Vb가 공백을 사이에 두고 주어진다. (1 ≤ Va, Vb ≤ V, Va ≠ Vb)

서로 다른 두 연결 구간 (Va1, Vb1), (Va2, Vb2) 에서 Va1 = Va2 & Vb1 = Vb2 인 경우는 존재하지 않으며, 임의의 지점에 적어도 하나의 연결 구간이 연결되어 있음이 보장된다.

출력

종우가 원하는 노선을 만들 수 있다면 YES, 아니면 NO를 출력한다.

내 코드

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

public class Main {

    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static int[] degree;

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

        int V = Integer.parseInt(st.nextToken()); // 정점 수
        int E = Integer.parseInt(st.nextToken()); // 간선 수

        graph = new ArrayList[V + 1];
        visited = new boolean[V + 1];
        degree = new int[V + 1];

        for (int i = 1; i <= V; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a);
            degree[a]++;
            degree[b]++;
        }

        // 간선이 연결된 아무 정점에서 DFS 시작
        int start = -1;
        for (int i = 1; i <= V; i++) {
            if (degree[i] > 0) {
                start = i;
                break;
            }
        }

        // 간선이 하나도 없는 경우 → YES
        if (start == -1) {
            System.out.println("YES");
            return;
        }

        // 연결 여부 확인
        dfs(start);

        for (int i = 1; i <= V; i++) {
            if (degree[i] > 0 && !visited[i]) {
                System.out.println("NO");
                return;
            }
        }

        // 홀수 차수 정점 개수 세기
        int odd = 0;
        for (int i = 1; i <= V; i++) {
            if (degree[i] % 2 != 0) {
                odd++;
            }
        }

        // 오일러 경로 또는 회로 조건
        if (odd == 0 || odd == 2) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }

    static void dfs(int v) {
        visited[v] = true;
        for (int u : graph[v]) {
            if (!visited[u]) {
                dfs(u);
            }
        }
    }
}