백준 25379번 구호물자 Java

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

문제

---

생각하기

---

동작

결과

코드

---

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N;
    private static List<List<Integer>> adjList;
    private static boolean[] isVisited;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        boolean ret = DFS(1);
        if (ret) {
            sb.append("CYCLE");
        } else {
            sb.append("NO CYCLE");
        }

        return sb.toString();
    } // End of solve()

    private static boolean DFS(int node) {
        if (isVisited[node] && !adjList.get(node).isEmpty()) {
            return true;
        }

        isVisited[node] = true;
        for (int next : adjList.get(node)) {
            if (DFS(next)) return true;
        }

        isVisited[node] = false;
        return false;
    } // End of DFS()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());

        adjList = new ArrayList<>();
        isVisited = new boolean[N + 1];
        for (int i = 0; i <= N; i++) {
            adjList.add(new ArrayList<>());
        }

        for (int i = 1; i < N; i++) {
            int M = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                adjList.get(i).add(Integer.parseInt(st.nextToken()));
            }
        }
    } // End of input()
} // End of Main class

플로이드 워셜

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N;
    private static int[][] arr;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        floyd();
        for (int i = 1; i < N; i++) {
            if (arr[1][i] == 1 && arr[i][i] == 1) {
                sb.append("CYCLE");
                return sb.toString();
            }
        }

        sb.append("NO CYCLE");
        return sb.toString();
    } // End of solve()

    private static void floyd() {

        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (arr[i][k] == 1 && arr[k][j] == 1) {
                        arr[i][j] = 1;
                    }
                }
            }
        }

    } // End of floyd()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());

        arr = new int[N + 1][N + 1];

        for (int i = 1; i < N; i++) {
            int M = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                arr[i][Integer.parseInt(st.nextToken())] = 1;
            }
        }
    } // End of input()
} // End of Main class