백준 11562번(JAVA)

반응형

플로이드 와샬 문제이다. 항상 플로이드 와샬은 간선의 가중치를 행렬에 저장하는 식이었는데 이번에는 간선의 가중치가 아니라 다르게 접근하면 된다.

map[n+1][n+1]을 일단 Integer.MAX_VALUE로 채워준다. map[n+1][n+1]은 long형식으로 설정해줘야지 오버플로우가 안 발생한다.

예를 들어 입력을 받을때 u에서 v로가는 일방통행 도로가 있다고 하면 map[u][v]=0이다.

하지만 map[v][u]는 어떻게 설정해야 할까

일방통행 도로를 양방향으로 바꿔줘야한다. 즉, u에서 v로가는 일방통행도로 1개를 양방향으로 바꿔주면 되므로 

map[v][u]=1이다.

입력을 받을때 이 점을 유의해서 받아준다.

그 후 3중 for문을 실행해준다.

한 기점(내 소스코드에서는 i로 설정) map[j][i]+map[i][k]를 temp로 둔다. map[j][i]로 가는데 양방향으로 바꿔야하는 도로가 1개 map[i][k]로 가는데 양방향으로 바꿔야하는 도로가 1개이면 map[j][k],즉 j에서 k로 가는데 양방향으로 바꿔야하는 도로는 2개이다. map[j][k]=Math.min(map[j][k],temp);를 실행해준다.

 

소스코드

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));
		String[] s=br.readLine().split(" ");
		int n=Integer.parseInt(s[0]);
		int m=Integer.parseInt(s[1]);
		long[][] map=new long[n+1][n+1];
		for(int i=1;i<=n;i++)
		{
			Arrays.fill(map[i], Integer.MAX_VALUE);
		}
		for(int i=0;i<m;i++)
		{
			s=br.readLine().split(" ");
			int u=Integer.parseInt(s[0]);
			int v=Integer.parseInt(s[1]);
			int b=Integer.parseInt(s[2]);
			if(b==0)//단방향
			{
				map[u][v]=0;
				map[v][u]=1;//v에서 u로 가려면 u에서 v로가는 일방통행 도로 1개를 양방향으로 바꿔줘야한다 
			}
			else//양방향
			{
				map[u][v]=0;
				map[v][u]=0;
			}
		}
		for(int i=1;i<=n;i++)//i번에서 i번으로는 도로를 바꿀 필요가 없으므로 0
		{	
			map[i][i]=0;
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				for(int k=1;k<=n;k++)
				{
					long temp=map[j][i]+map[i][k];
					map[j][k]=Math.min(map[j][k], temp);
				}
			}
		}
		int k=Integer.parseInt(br.readLine());
		StringBuilder result=new StringBuilder();
		for(int i=0;i<k;i++)
		{
			s=br.readLine().split(" ");
			int S=Integer.parseInt(s[0]);
			int E=Integer.parseInt(s[1]);
			result.append(map[S][E]+"\n");
		}
		System.out.println(result.toString());
	}
}

 

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

 

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