백준 2458 java

플로이드 워셜 알고리즘을 사용했다. 이번에는 최소비용을 구하는게 아니고, 길이 존재하는지만 확인했다. 메모리와 수행시간이 다른 풀이에 비해 큰데 Scanner 클래스 때문인거 같다.

import java.util.Scanner;
import java.util.Vector;

public class bj2458 {
    static Scanner scanner = new Scanner(System.in);
    static boolean [][] graph;

    public static void main(String[] args) {

        //플로이드 와샬 알고리즘 사용
        inputData();
        findAnswer();

        scanner.close();
    }

    public static void inputData()
    {
        //System.out.println("inputData()");
        int i;
        int a, b;
        int N, M;

        N = scanner.nextInt();
        M = scanner.nextInt();
        graph = new boolean[N + 1][N + 1];
        for(i = 0; i < M; i++)
        {
            a = scanner.nextInt();
            b = scanner.nextInt();
            graph[a][b] = true;//크기 비교니까 양방향이 아니라 단방향
        }

//        System.out.println("입력결과");
//        for(i = 1; i < graph.length; i++)
//        {
//            for(int j = 1; j < graph[i].length; j++)
//            {
//                System.out.print(graph[i][j] + " ");
//            }
//            System.out.println();
//        }
    }

    public static void findAnswer()
    {
        //System.out.println("findAnswer()");
        int i, j, k, count = 0;
        int [] answer = new int[graph.length];

        for(k = 1; k < graph.length; k++)
        {
            for(i = 1; i < graph.length; i++)
            {
                for(j = 1; j < graph.length; j++)
                {
                    if(graph[i][k] && graph[k][j])
                    {
                        graph[i][j] = true;
                    }
                }
            }
        }

//        System.out.println("순회결과");
//        for(i = 1; i < graph.length; i++)
//        {
//            for(j = 1; j < graph[i].length; j++)
//            {
//                System.out.print(graph[i][j] + " ");
//            }
//            System.out.println();
//        }

        for(i = 1; i < graph.length; i++)
        {
            for(j = 1; j < graph.length; j++)
            {
                if(graph[i][j] || graph[j][i])//크기 순서를 알 수 있다면
                {
                    answer[i]++;
                }
            }
        }

//        System.out.println("answer 저장결과");
//        for(i = 1; i < answer.length; i++)
//        {
//            System.out.print(answer[i] + " ");
//        }
//        System.out.println();

        for(i = 1; i < answer.length; i++)
        {
            //자기 키가 몇번째인지 알 수 있는 학생이 필요한 거니,
            //자기를 제외한 모든 사람의 순서에 대해 알면 자기 키가 몇번째인지 아는 거임
            if(answer[i] == graph.length - 2)//graph.length = 6 + 1 = 7, 자기를 제외한 모든 순서는 5
            {
                count++;
            }
        }
        System.out.println(count);
    }
}