[BOJ] 11403번 경로 찾기

문제

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

11403번: 경로 찾기

 

 

풀이

이 문제를 처음 접근할 때는 각 시점과 목적점을 사용하여 DFS로 풀었었다. 하지만 실행시간이 오래 걸리고, 메모리도 많이 쓰는 방식을 썼던 것 같아서 다른 방법을 찾던 중 다른 분이 포스팅했던 글을 보고 Floyd-Warshall 알고리즘을 이용하여 갈 수 있는 방법을 초기화해주는 방식으로 하면 실행시간을 줄일 수 있는 것을 알게 되었다.

 

1) DFS

 

import java.util.*;
 
public class Main {
    static Scanner scan = new Scanner(System.in);
    static int[][] array;
    static boolean[] visited;
    static boolean flag;
    static int N;
 
    static void solution() {
        N = scan.nextInt();
        array = new int[N][N];
        visited = new boolean[N];
        //입력
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++)
                array[i][j] = scan.nextInt();
        }
        //계산
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                reset_visit();
                flag = false;
                dfs(i,j);
                if(flag)
                    System.out.print("1 ");
                else
                    System.out.print("0 ");
            }
            System.out.println();
        }
        
    }
    static void dfs(int from, int dest) {
        for(int i=0;i<N;i++) {
            if(array[from][i] == 1 && !visited[i]) {
                if(i==dest) {
                    flag = true;
                    return;
                }
                visited[i] = true;
                dfs(i,dest);
            }
        }
    }
    static void reset_visit() {
        for(int i=0;i<N;i++)
            visited[i] = false;
    }
    public static void main(String[] args) {
        solution();
    }
}
 

2) Floyd-Warshall 

 

import java.util.*;
 
public class Main {
    static Scanner scan = new Scanner(System.in);
    static int[][] array;
    static int N;
 
    static void solution() {
        N = scan.nextInt();
        array = new int[N][N];
    
        //입력
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++)
                array[i][j] = scan.nextInt();
        }
        //계산
        for(int p = 0;p<N;p++) {
            for(int i=0;i<N;i++) {
                for(int j=0;j<N;j++) {
                    if(array[i][p]==1 && array[p][j] == 1)
                        array[i][j] = 1;
                }
            }
        }
        
        //출력
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++)
                System.out.print(array[i][j]+" ");
            System.out.println();
        }
        
    }
    
 
    public static void main(String[] args) {
        solution();
    }
}