플로이드 워셜 알고리즘을 사용한다.
구현이 잘 안되어 여러 군데 참고했다.
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);
}
}
}