[백준] 1613 - 역사 (JAVA)

정보

1. 소요시간 : 20분.
2. 문제 수준 : 골드 3
3. 문제 유형 : 그래프 이론, 플로이드 - 워셜
4. 문제 사이트 : 백준
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/1613
8. 푼 날짜 : 2023.03.06

1. 사용한 자료구조 & 알고리즘

전형적인 플로이드 - 워셜 알고리즘의 문제였다.
n이 400 이하의 자연수이고, 플로이드 - 워셜 알고리즘의 시간복잡도는 O(n^3) 이므로, 최대 400 x 400 x 400 으로 64,000,000 이다. 100,000,000 이 대략 1초이고, 문제의 시간 제한이 1초이니 시간제한에 걸리지도 않을 것으로 예상했다.

2. 풀이과정

플로이드 - 워셜 알고리즘에 대한 이해만 있다면 누구나 풀 수 있는 문제이므로
이 알고리즘을 모른다면 공부하고 오는 것을 추천한다.
플로이드 - 워셜 알고리즘은 모든 정점에서 다른 정점으로 가는 최단 거리를 구하는 알고리즘이다.

• 풀이

1. 플로이드 - 워셜 알고리즘으로 다른 정점으로 가는 최단 거리를 구한다.
2. 그 후 , 알고싶은 정보의 개수 s 만큼 입력을 받는다.
3. 만약, 노드 A에서 노드 B로 가는 거리가 무한이고, 노드 B에서 노드 A로 가는 거리도 무한이라면 두 관계를 서로 알 수 없으므로 0을 출력
4. 노드 A에서 노드 B로 가는 거리가 무한이 아니라면, 즉, 양수라면 노드 A에서 노드 B로 갈 수 있고, 이 경우에는 -1을 출력한다. 두 노드가 서로 INF 인 경우는 3번에서 걸렀으므로 한 노드에서만 다른 노드로 향할 수 있음을 알 수 있다.
5. 그 외에는 1을 출력한다.

3. 소스코드

import java.io.*;
import java.util.*;



public class Main{
	static int INF=100000000;

	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb=new StringBuilder();


		st=new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());

		int dist[][]=new int[n+1][n+1];
		for(int i=0;i<dist.length;i++) {
			for(int j=0;j<dist.length;j++) {
				if(i!=j) dist[i][j] =INF;
			}
		}
		for(int i=0;i<m;i++) {
			st=new StringTokenizer(br.readLine());
			int node1=Integer.parseInt(st.nextToken());
			int node2=Integer.parseInt(st.nextToken());
			dist[node1][node2]=1;
		}
		for(int i=1;i<dist.length;i++) {
			for(int j=1;j<dist.length;j++) {
				for(int k=1;k<dist.length;k++) {
					dist[j][k]=Math.min(dist[j][k], dist[j][i]+dist[i][k]);
				}
			}
		}

		int s=Integer.parseInt(br.readLine());
		
	
		for(int i=0;i<s;i++) {
			st=new StringTokenizer(br.readLine());
			int node1=Integer.parseInt(st.nextToken());
			int node2=Integer.parseInt(st.nextToken());
			if(dist[node1][node2]==INF&&dist[node2][node1]==INF)
				sb.append(0);
			else if(dist[node1][node2]!=INF)
				sb.append(-1);
			else 
				sb.append(1);
			sb.append("\n");
		}
		System.out.println(sb);


	}

}

4. 회고

플로이드 - 워셜 알고리즘과 다익스트라 알고리즘은 이제 사용이 익숙한데, 벨만-포드 알고리즘에 대해서는 아직 이해가 많이 부족하다. 곧 벨만-포드 알고리즘 문제인 웜홀도 풀어 볼 예정이다. solved.ac 클래스 4에도 내장되어 있는 문제로, 그만큼 중요도가 높은 문제인 것 같다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고 있다.
https://solved.ac/profile/anwlro0212