[BJ]11581 구호물자

BJ S1 11581 구호물자

 

 

문제링크

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

11581번: 구호물자

 

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/N2UlLDbgJ0g

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * @author 은서파
 * @since 2022/04/10
 * @see
 * @git
 * @youtube
 * @performance 11936 84, 12336	96
 * @category #
 * @note
 */

public class BJ_S1_11581_구호물자 {
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder output = new StringBuilder();
    private static StringTokenizer tokens;

    private static int N;
    private static boolean[][] graph;
    private static int[] visited;

    private static boolean isCycle;

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        N = Integer.parseInt(input.readLine()) + 1;
        graph = new boolean[N][N];

        for (int i = 1; i < N - 1; i++) {
            int M = Integer.parseInt(input.readLine());
            tokens = new StringTokenizer(input.readLine());
            // 단방향 그래프
            for (int m = 0; m < M; m++) {
                graph[i][Integer.parseInt(tokens.nextToken())] = true;
            }
        } // 입력 완료

        visited = new int[N];
        // dfs(1);
        floyd();
        System.out.println(isCycle ? "CYCLE" : "NO CYCLE");
    }

    private static void dfs(int v) {
        // 1. 방문 처리
        visited[v] = 1; // 단순 방문 - 종료되지 않은 상태

        // 2. 자식 탐색
        for (int i = 1; i < N; i++) {
            if (graph[v][i]) {
                if (visited[i] == 0) {
                    dfs(i);
                } else if (visited[i] == 1) {
                    isCycle = true;
                    return;
                }
            }
        }

        // 3. 모든 자식 탐색 완료 - 작업 종료
        visited[v] = 2;
    }

    private static void floyd() {
        for (int via = 1; via < N; via++) {
            for (int from = 1; from < N; from++) {
                if (!graph[from][via]) {
                    continue;
                }
                for (int to = 1; to < N; to++) {
                    if (graph[via][to]) {
                        graph[from][to] = true;
                    }
                }
            }
        }
        /*
        for (boolean[] row : graph) {
            System.out.println(Arrays.toString(row));
        }*/
        for(int i=1; i<N; i++){
            if(graph[1][i] && graph[i][i]){
                isCycle =  true;
                return;
            }
        }
    }

    // REMOVE_START
    private static String src = "3\r\n" +
                                "2\r\n" +
                                "2 3\r\n" +
                                "1\r\n" +
                                "3";
    // REMOVE_END
}