플로이드 워셜 - Java

chaemin·2024년 4월 3일

이것이코딩테스트다 최단경로 플로이드워셜

이것이 코딩테스트다

목록 보기

3/8

플로이드 워셜

=모든 지점에서 다른 모든 지점까지의 최단 경로

따라서 2차원 리스트에 '최단 거리' 정보를 저장한다는 특징이 있다.
최단거리 찾기 중 범위가 적으면 플로이드 워셜을 사용하는게 좋다.

자기 자신은 0, 그 이외는 무한대로 초기화 해준다.

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(i == j)
                    map[i][j] = 0;
                
                else
                    map[i][j] = (int)1e9;
            }
        }

간선의 정보를 저장한다.

		for(int i = 0; i < m; i++) {
            
            int a = input.nextInt();
            int b = input.nextInt();
            int c = input.nextInt();
            
            //map[a][b] = c;
            //아 0인 것들도 있으니까..? 근데 왜 굳이 이 min을 해야하는거지..?
            map[a][b] = Math.min(c, map[a][b]);
        }

거쳐가는 노드를 먼저 중심으로
모든 노드에서의 최단 거리를 구한다.

        for(int k = 1; k <= n; k++) {
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                }
            }
        }

[플로이드]

1-1. [플로이드] 문제

https://www.acmicpc.net/problem/11404

1-2. 풀이

여기서의 핵심 포인트는 바로 중복된 출발도시와 도착도시 입니다.
입력 조건에

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

라고 되어있기 때문에

1 4 2
1 4 1

이렇게 들어올 수 있기 때문입니다. 따라서 저장된 값의 min을 통해 가장 작은 값을 저장합니다.

1-3. 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		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+1][n+1];
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(i == j) {
					map[i][j] = 0;
				} else {
					map[i][j] = (int)1e9;
				}
			}
		}
		
		for(int i = 0; i < m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			map[a][b] = Math.min(c, map[a][b]);
		}
		
		for(int k = 1; k <= n; k++) {
			for(int a = 1; a <= n; a++) {
				for(int b = 1; b <= n; b++) {
					map[a][b] = Math.min(map[a][b], map[a][k] + map[k][b]);
				}
			}
		}
		
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(map[i][j] == (int)1e9) {
					map[i][j] = 0;
				}
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}

	}

}

[경로찾기]

2-1. [경로 찾기] 문제

https://www.acmicpc.net/problem/11403

2-2. 풀이

최소경로가 아니라 유무만 판단하는 것이다! 따라서
단순히 갈 수 있는지만 판단한다.

for(int k = 0; k < N; k++) {
	for(int a = 0; a < N; a++) {
		for(int b = 0; b < N; b++) {
			//map[a][b] = Math.min(map[a][b], map[a][k] + map[k][b]);
			if(map[a][k] == 1 && map[k][b] == 1) {
				map[a][b] = 1;
			}
		}
	}
}

2-3. 코드

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

public class 플로이드워셜_11403 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int map[][] = new int[N][N];
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			
			for(int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int k = 0; k < N; k++) {
			for(int a = 0; a < N; a++) {
				for(int b = 0; b < N; b++) {
					//map[a][b] = Math.min(map[a][b], map[a][k] + map[k][b]);
					if(map[a][k] == 1 && map[k][b] == 1) {
						map[a][b] = 1;
					}
				}
			}
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}

	}
}

[케빈 베이컨의 6단계]

3-1. [케빈 베이컨의 6단계] 문제

https://www.acmicpc.net/problem/1389

3-2. 풀이

친구들 사이의 관계를 1로 두고 플로이드 워셜을 진행하면 된다.

3-3. 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int map[][] = new int[n+1][n+1];
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(i == j) {
					map[i][j] = 0;
				} else {
					map[i][j] = (int)1e9;
				}
			}
		}
		
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			map[a][b] = 1;
			map[b][a] = 1;
		}
		
		for(int k = 1; k <= n; k++) {
			for(int a = 1; a <= n; a++) {
				for(int b = 1; b <= n; b++) {
					map[a][b] = Math.min(map[a][b], map[a][k] + map[k][b]);
				}
			}
		}
		
		int min = Integer.MAX_VALUE;
		int answer = 0;
		
		for(int i = 1; i <= n; i++) {
			int result = 0;
			for(int j = 1; j <= n; j++) {
				result += map[i][j];
			}
			if(min > result) {
				min = result;
				answer = i;
			}
		}
		System.out.println(answer);
	}

}

[정확한 순위]

4-1. [정확한 순위] 문제

선생님은 시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부만 가지고 있습니다. 학생 N명의 성적은 모두 다륻데, 다음은 6명의 학생에 대하여 6번만 성적을 비교한 결과 입니다.

1번 학생 성적 < 5번 학생 성적

3번 학생 성적 < 4번 학생 성적

4번 학생 성적 < 2번 학생 성적

4번 학생 성적 < 6번 학생 성적

5번 학생 성적 < 2번 학생 성적

5번 학생 성적 < 4번 학생 성적

A번 학생의 성적의 성적이 B번 학생보다 낮다면 화살표가 A에서 B를 가리키도록 할 때 위의 성적 결과를 다음 그림처럼 표현할 수 있습니다.

이 그림으로 유추해서 순위를 정확히 알 수 있는 학생도 있고, 알 수 없는 학생도 있습니다. 예를 들어 1번 학생은 5번 학생보다 성적이낮고, 5번 학생은 4번 학생보다 성적이 낮으므로 1번 학생은 4번 학생보다 성적이 낮습니다. 따라서 1번, 3번, 5번 학생은 모두 4번 학생보다 성적이 낮다고 볼 수 있습니다. 그리고 4번 학생은 2번 학생과 6번 학생보다 성적이 낮습니다. 정리하면 4번 학생보다 성적이 낮은 학생은 3명이고, 성적이 높은 학생은 2명이므로 4번 학생의 성적 순위를 정확히 알 수 있습니다. 하지만 예시에서 4번 학생을 제외한 다른 학생은 정확한 순위를 알 수 없습니다.

학생들의 성적을 비교한 결과가 주어질 때, 성적 순위를 정확히 알 수 있는 학생은 모두 몇명인지 계산하는 프로그램을 작성하세요.

입력 조건

첫째 줄에 학생들의 수 N(2 <= N <= 500)과 두 학생의 성적을 비교한 횟수 M(2 <= M <= 10,000)이 주어집니다.
다음 M개의 각 줄에는 두 학생의 성적을 비교한 결과를 나타내는 두 양의 정수 A와 B가 주어집니다.
이는 A번 학생의 성적이 B번 학생보다 낮다는 것을 의미합니다.

출력조건

첫째 줄에 성적 순위를 정확히 알 수있는 학생이 몇 명인지 출력합니다.

입력 예시

출력 예시

4-2. 풀이

범위가 적기 때문에 플로이드 워셜을 사용해서 문제를 풀이한다.

✨A에서 B로 도달이 가능 하거나 || B에서 A로 도달 가능할 경우 count + 1을 수행한다.
if(map[i][j] != (int)1e9 || map[j][i] != (int)1e9 ) {
	count += 1;
}

4-3. 코드

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

public class 플로이드워셜_정확한순위 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int map[][] = new int[N+1][N+1];
		
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= N; j++) {
				if(i == j) {
					map[i][j] = 0;
				} else {
					map[i][j] = (int)1e9;
				}
			}
		}
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			map[A][B] = 1;
		}
		
		for(int k = 1; k <= N; k++) {
			for(int a = 1; a <= N; a++) {
				for(int b = 1; b <= N; b++) {
					map[a][b] = Math.min(map[a][b], map[a][k] + map[k][b]);
				}
			}
		}
		
		int answer = 0;
		for(int i = 1; i <= N; i++) {
			int count = 0;
			for(int j = 1; j <= N; j++) {
				if(map[i][j] != (int)1e9 || map[j][i] != (int)1e9 ) {
					count += 1;
				}
			}
			if(count == N) {
				answer += 1;
			}
		}
		System.out.println(answer);
	}

}

chaemin

Hi!

이전 포스트

정렬 - 두 배열의 원소 교체

다음 포스트