백준 10159 java

magicdrill·2024년 10월 9일
0

백준 문제풀이

목록 보기
459/654

백준 10159 java

플로이드 워셜 알고리즘을 사용한다.
구현이 잘 안되어 여러 군데 참고했다.
https://blog.naver.com/ndb796/221234427842?trackingCode=blog_bloghome_searchlist
객체 모듈형으로 만들어 보려했는데 해결 못 했다.

import java.util.Scanner;

public class bj10159 {
    static Scanner scanner = new Scanner(System.in);

    //플로이드 워셜 알고리즘
    public static void main(String[] args) {

        int[][] data = inputData();
        findAnswer(data);
    }

    public static int[][] inputData()
    {
        //System.out.println("inputData()");
        int i, a, b;
        int N;//물건의 개수
        int M;//측정된 물건 쌍의 개수
        int[][] data;

        N = scanner.nextInt();
        M = scanner.nextInt();
        data = new int[N + 1][N + 1];
        for(i = 0; i < M; i++)
        {
            a = scanner.nextInt();
            b = scanner.nextInt();
            //a가 b보다 무거움
            data[a][b] = 1;
            data[b][a] = 2;
        }

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

        return data;
    }

    public static void findAnswer(int [][] data)
    {
        //System.out.println("findAnswer()");
        int i, j, k, count;

        //플로이드 워셜
        for(k = 1; k < data.length; k++)
        {
            for(i = 1; i < data.length; i++)
            {
                for(j = 1; j < data.length; j++)
                {
                    if(data[i][k] == 1 && data[k][j] == 1)
                    {
                        data[i][j] = 1;
                    }
                    else if(data[i][k] == 2 && data[k][j] == 2)
                    {
                        data[i][j] = 2;
                    }
                }
            }
        }

//        System.out.println("플로이드 와샬 결과");
//        for(i = 0; i < data.length; i++)
//        {
//            for(j = 0; j < data.length; j++)
//            {
//                System.out.print(data[i][j] + " ");
//            }
//            System.out.println();
//        }

        for(i = 1; i < data.length; i++)
        {
            count = 0;
            for(j = 1; j < data.length; j++)
            {
                if(i != j && data[i][j] == 0)
                {
                    count++;
                }
            }
            System.out.println(count);
        }
    }
}

0개의 댓글