[Java] 백준(실버-1) 11403번 - 경로 찾기
문제 풀이
이 문제는 플로이드 워셜 알고리즘을 이용해 풀 수 있는 문제이다.
아이디어 도출
플로이드 워셜 알고리즘은 모든 정점에서 모든 정점으로의 최단거리를 구하는 알고리즘이다. 문제에서 요구하는 경로 확인을 위해서는 플로이드 워셜 알고리즘을 이용해 거쳐가는 정점을 확인해야 한다.
이 거쳐 가는 정점을 기준으로 최단 거리를 구할 수 있다. 이 말은 즉, i에서 j까지 가는 길이 있는지 확인하려면 i에서 k로 가고, k에서 j로 가는 길이 있으면 된다라고 볼 수 있다.
이는 문제에서 i에서 j로 갈 수 있는 경로가 있는지 판단해야하는 것과 완전히 부합한다. 이제 문제 풀이를 위한 아이디어를 생각해보자.
- 그래프를 입력받는다.
- 3중 반복문을 통해 거쳐가는 정점을 확인(k가 0, 1, … , N - 1일 때까지 설정)해가며, i에서 k로 가는길과 k에서 j로 가는길이 있는지(==1) 확인한다.
- i -> k, k -> j로 가는 길이 있다면 i에서 j로 가는길이 있는 것이기에 해당 위치를 1로 갱신한다.
- 위 갱신 작업을 마친 후의 그래프를 출력한다.
이번 문제에서는 단순히 i에서 j로 갈 수 있는지만 체크하면 되기에 쉽게 풀 수 있다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
int N = Integer.parseInt(br.readLine());
int[][] arr = new int[N][N];
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
/**
* 플로이드 워셜을 통해 거쳐가는 정점 확인
* i에서 j까지 갈 수 있는지는 i에서 k로, k에서 j로 갈 수 있는지를 확인한다.
* 갈 수 있다면, 해당 위치를 1로 갱신한다.
*/
for(int k=0; k<N; k++) {
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(arr[i][k] == 1 && arr[k][j] == 1) {
arr[i][j] = 1;
}
}
}
}
for(int[] a : arr) {
for(int n : a) {
bw.write(n+ " ");
}
bw.write("\n");
}
}
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.