[백준] 11403번 경로 찾기 - Java, 자바

난이도

실버 1

문제

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

풀이

이 문제는 플로이드 와샬을 활용한 문제이다.
플로이드 와샬에 대해 먼저 학습하고 문제를 풀기를 추천한다.

플로이드 와샬이란 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다.
플로이드 와샬의 핵심 아이디어는 '거쳐 가는 정점'을 기준으로 최단 거리를 구하는 것이다.
즉 i에서 j까지 가는 것과 i에서 k로 가고 k에서 j로 가는 것은 같다는 의미이다.

따라서 거쳐가는 정점인 k가 0일 때, 1일때 ~n-1일 때 성정해놓고
map[i][k]==1&&map[k][j]==1인 경우, map[i][j]=1로 초기화하면 된다.

코드

package 그래프탐색;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ11403 {
    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());
            }
        }

        // i에서 j까지 갈 수 있는가?
        // i에서 k로 가고, k에서 j로 갈 수 있는가?
        for (int k = 0; k < n; k++) { // 거쳐갈 노드
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    // 단순히 갈 수 있는 경로가 있는지만 체크
                    if (map[i][k] == 1 && map[k][j] == 1) {
                        map[i][j] = 1;
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sb.append(map[i][j] + " ");
            }
            sb.append("\n");
        }
        System.out.println(sb);

    }
}

https://steady-coding.tistory.com/94