[백준/JAVA] 11403번: 경로 찾기

🔺 문제

11403번: 경로 찾기

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[][] distance;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        distance = new int[N + 1][N + 1];
        
        for(int i = 1 ; i <= N ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            for(int j = 1 ; j <= N ; j++) {
                distance[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 플로이드-워셜
        for(int k = 1 ; k <= N ; k++) {
            for(int i = 1 ; i <= N ; i++) {
                for(int j = 1 ; j <= N ; j++) {
                    if(distance[i][k] == 1 && distance[k][j] == 1) 
                        distance[i][j] = 1;
                }
            }
        }
        
        // 출력
        for(int i = 1 ; i <= N ; i++) {
            for(int j = 1 ; j <= N ; j++) {
                System.out.print(distance[i][j] + " ");
            }
            System.out.println();
        }
    }
}

✅ 해결 아이디어
✔ 플로이드-워셜
- 최단 거리 배열 업데이트 시 조건 변형 : if(distance[i][k] == 1 && distance[k][j] == 1)일 때, distance[i][j] 로 업데이트

 

 

---

🔺 다른 풀이들

- 출력 StringBuilder로 하면 메모리가 더 줄지요

[백준] 11403번: 경로 찾기 - JAVA

 

---

💬 느낀 점

이렇게 3중 for문 하는 알고리즘 이름을 플로이드-워셜이라고 하는구나... 싶었다.

 

 

 

1회독	2회독	3회독	4회독	5회독
V	6/26

 

 

(+ 6/26 2회독)

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[][] dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        N = Integer.parseInt(br.readLine());
        
        // 최단 경로 배열 선언 · 초기화
        dp = new int[N][N];
        
        // 인접 행렬 채우기
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                dp[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        // 플로이드-워셜
        for(int k = 0 ; k < N ; k++) {
            for(int i = 0 ; i < N ; i++) {
                for(int j = 0 ; j < N ; j++) {
                    // 🔔 중간 경로 중 1개라도 연결되어 이다면, 연결 노드로 저장 🔔
                    if(dp[i][k] == 1 && dp[k][j] == 1) {
                        dp[i][j] = 1;
                    }
                }
            }
        }
        
        // 출력
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                sb.append(dp[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}