(Java) 백준 11403 경로 찾기

문제 링크

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

나의 기록

✅ 알고리즘 분류 : 플로이드-와샬

✅ 성공 여부 : ✔

✅ 문제 난이도 : 실버1

✅ 체감 난이도 : Normal

접근 방법

i노드에서 j노드까지 접근 가능한지 알아보려고 DFS 쓰면.... 시간초과 난다!

 

플로이드-와샬 알고리즘을 사용해 코드량도 줄였고 시간초과도 해결했다.

i노드와 k노드가 연결되어 있고(adjMatrix[i][k] == 1), k노드와 j노드가 연결되어 있으면(adjMatrix[k][j] == 1)

i노드와 j노드가 인접한 것으로 취급하여 1로 바꿔준다.

 

이렇게 3중 for문을 돌며 수정한 adjMatirix가 그대로 답이 된다.

 

코드

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

public class bj11403_경로찾기 {
    static int N;
    static int[][] adjMatrix;

    public static void main(String[] args) throws IOException {
        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        adjMatrix = new int[N][N];
        for(int i = 0 ; i < N ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < N ; j++){
                adjMatrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 답 찾기
        // k : 거쳐 가는 노드, i : 출발 노드, j : 도착 노드
        for(int k = 0 ; k < N ; k++){
            for(int i = 0 ; i < N ; i++){
                for(int j = 0 ; j < N ; j++){
                    // i와 k가 연결되어 있고, k와 j가 연결되어 있는가? (가중치는 상관없음)
                    if(adjMatrix[i][k] == 1 && adjMatrix[k][j] == 1){
                        // i와 j가 연결된 것으로 친다.
                        adjMatrix[i][j] = 1;
                    }
                }
            }
        }

        // 출력
        for(int i = 0 ; i < N ; i++){
            StringBuilder sb = new StringBuilder();
            for(int j = 0 ; j < N ; j++){
                sb.append(adjMatrix[i][j] + " ");
            }
            System.out.println(sb.toString());
        }
    }
}