백준 11403번
https://www.acmicpc.net/problem/11403
문제
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.
출력
총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.
생각하기
Floyd-Warshall 맛보기
경로를 찾는 Floyd-Warshall 알고리즘의 기초 문제이다.
원래 플로이드 워셜 알고리즘의 최단 경로의 길이(가중치의 합)을 찾는 것이 목적인데,
이 문제는 단순히 방향 그래프에서 각 노드간에 이동할 수 있는지 없는지를 파악하는 문제였다.
진짜 기초를 다지기 위한 문제 너무 좋았음.
풀다 보니 느낀점은
동적 계획법도 들어가있고, 사실 부르트포스 개념도 들어가 있는 것 같다
그래프 전체를 완전탐색해서 노드간에 이동이 가능한지를 파악하는 것,
또한, 한번 노드간 이동이 가능하다는 것을 파악한 이후 부터는 1로 기록을 해서 다른 노드로 이동 가능하다는 것을 알 수 있다는 점
동작
우리가 일상 생활을 할때, 강을 건넌다고 생각해보자.
A -> B로 이동할 때, 다리를 건넌다고 한다면, 다리가 여기서 k의 개념이라고 생각하면 쉬울 것 같다
결국 어떤 곳으로 이동할 때, 하나씩 파악해서 다리가 하나라도 있으면 하나씩 하나씩 다리를 건너서(경로가 멀 지라도) 이동할 수 있는지 여부를 파악한다고 생각하면 쉽다
Find_Road() 함수가 경로를 찾게 해주는 함수이다.
for(int k=0; k<N; k++) {
// i = 출발 노드
for(int i=0; i<N; i++) {
// j = 도착 노드
for(int j=0; j<N; j++) {
// (i,k) -> (k, j) -> (k,i) 방향 그래프에서 다른 간선과 노드를 통해
// 해당 노드로 이동이 가능한 가 를 판별
if(arr[i][k] == 1 && arr[k][j] == 1) {
arr[i][j] = 1;
}
}
}
}해당 부분에서 k를 통해서 하나씩 이동 할 수 있는지 노드 사이에 연결되는 곳이 있는지를 파악하고
우리가 만들어놓은 arr행렬에서 갈 수 있다를 1로 기록해 놓으면
하나씩 arr에 1이 생기면서 전체를 탐색해서 갈 수 있는 노드간에
간선을 행렬로 표시해서 완성시키는 개념이다.
각 지역마다 갈 수 있냐 없냐를 지도로 만든다고 생각해보자.
어렵지 않게 이해할 수 있을 것이라고 믿는다!
코드
import java.io.*;
public class Main {
// input
private static BufferedReader br;
// variables
private static int N;
private static int[][] arr;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
input();
bw.write(solve());
bw.close();
} // End of main()
private static String solve() {
StringBuilder sb = new StringBuilder();
floyd();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sb.append(arr[i][j]).append(' ');
}
sb.append('\n');
}
return sb.toString();
} // End of solve()
private static void floyd() {
for (int i = 0; i < N; i++) { // 9번씩 0 9번
for (int j = 0; j < N; j++) { // 3번씩 0 3번
for (int k = 0; k < N; k++) { // 1번씩 0 1번
// (i, k) -> (k, j) -> (k, i)
if (arr[j][i] == 1 && arr[i][k] == 1) {
arr[j][k] = 1;
}
}
}
}
} // End of floyd()
private static void input() throws IOException {
N = Integer.parseInt(br.readLine());
arr = new int[N][N];
for (int i = 0; i < N; i++) {
String temp = br.readLine();
for (int j = 0; j < N; j++) {
arr[i][j] = temp.charAt(j << 1) - '0';
}
}
} // End of input()
} // End of Main class
>```
