백준 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이 생기면서 전체를 탐색해서 갈 수 있는 노드간에
간선을 행렬로 표시해서 완성시키는 개념이다.

각 지역마다 갈 수 있냐 없냐를 지도로 만든다고 생각해보자.
어렵지 않게 이해할 수 있을 것이라고 믿는다!

TMI

플로이드 워셜 시식코너..
...나름 괜찮을 지도?

코드

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

public class Main {
	static StringBuilder sb;
	static int N, M;

	static int arr[][];
	static boolean visit[][];

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

		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];

		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		Road_Finder();

		sb = new StringBuilder();
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                sb.append(arr[i][j] + " ");
            }
            sb.append("\n");
        }

        System.out.println(sb);

	} // End of Main

	static void Road_Finder() {

		// k = 거쳐가는 노드
		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;
					}
				}
			}
		}

	} // End of Find()
} // End of class