백준 10159번(JAVA)

반응형

플로이드-와샬 알고리즘을 이용하는 문제이다.

플로이드-와샬 알고리즘은 최단거리를 찾는 문제에서 가장 간단하다.

3중for문, 이것만 기억하면 된다. 3중for문이니까 당연히 시간복잡도는 O(v^3)이다.

그래서 보통 플로이드-와샬 알고리즘을 사용하는 문제들은 정점의 수가 1000을 넘지 않는 것 같다.

플로이드-와샬 알고리즘에 대한 기본적인 설명은 따로 하지 않겠다.

이 문제에서는 일단 입력을 받을때 1 2 이렇게 받으면 map[1][2]=1, map[2][1]=2 이렇게 했다.

1의 값은 앞에인덱스가 뒤에 인덱스보다 무겁다는 뜻, 2의 값은 앞에 인덱스가 뒤의 인덱스보다 보다 가볍다는뜻이다.

 

플로이드-와샬 알고리즘을 사용할때 기준점이 되는 k인덱스를 기준으로 map[i][k]==1&&map[k][j]==1 이면

i는 k보다 무겁고 k는 j보다 무거우므로 i는 j보다 무겁다. 그래서 map[i][j]==1이 된다.

반대로 map[i][k]==2&&map[k][j]==2 이면 i는 k보다 가볍고 k는 j보다 가볍다. 그래서 map[i][j]=2 가 된다.

아래 소스코드를 보면 이해가 쉬울 것이다.

소스코드

import java.util.*;
import java.io.*;
public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		int M=Integer.parseInt(br.readLine());
		int[][] map=new int[N][N];
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<N;j++)
			{
				if(i!=j)
				{
					map[i][j]=100000000;
				}
			}
		}
		String[] s;
		for(int i=0;i<M;i++)
		{
			s=br.readLine().split(" ");
			int a=Integer.parseInt(s[0])-1;
			int b=Integer.parseInt(s[1])-1;
			map[a][b]=1;//a가 b보다 무겁다는 뜻
			map[b][a]=2;//b가 a보다 가볍다는 뜻
		}
		for(int k=0;k<N;k++)
		{
			for(int i=0;i<N;i++)
			{
				for(int j=0;j<N;j++)
				{
					if(i!=j)
					{
						if(map[i][k]==1&&map[k][j]==1)
						{
							map[i][j]=1;
						}
						else if(map[i][k]==2&&map[k][j]==2)
						{
							map[i][j]=2;
						}
					}
					
				}
			}
		}
		for(int i=0;i<N;i++)
		{
			int count=0;
			for(int j=0;j<N;j++)
			{
				if(i!=j&&map[i][j]>=100000000)
				{
					count++;
				}
			}
			System.out.println(count);
		}

	}

}

댓글과 지적은 언제든지 환영입니다~!

 

글이 마음에 들었다면 왼쪽이미지를 눌러서 후원 부탁드립니다><