[백준 Java] 11403 경로 찾기

문제 링크

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

 

풀이

2가지 방법으로 풀었다.

dfs

• 한 행에 대해서 방문 배열 초기화
• 지금 행과 열이 1이라면 연속되는 곳을 찾기 위해 dfs 호출
• dfs 내에서 방문 처리, j에 대해서 연결된 다른 노드를 찾고 시작점과 이어주기 위해 dfs 호출

플로이드 워셜

• i와 k가 연결되고, k와 j가 연결된 경우 i와 j를 연결시켜줌

처음에는 플로이드 워셜이 생각 나지 않아 bfs, dfs 여러 방법으로 풀어봤었는데, 가중치가 없더라도 모든 간선을 확인하고, 연속해서 확인해야 하는 경우 플로이드 워셜을 사용하니 훨씬 더 간단하게 풀렸다. 또한 input이 100까지 들어오기 때문에 100^3번 수행한다.

아래는 dfs, 위에는 플로이드 워셜로 풀었는데 둘 다 100^3을 수행해서 메모리와 시간상 별 차이는 없다.

코드 1 - dfs

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

public class Main {
    static int N, map[][], res[][];
    static boolean[] v;

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

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

        for (int i = 0; i < N; i++) {
            tokens = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(tokens.nextToken());
            }
        }//end input

        for (int i = 0; i < N; i++) {
            v = new boolean[N];

            for (int j = 0; j < N; j++) {
                if(map[i][j] == 1 && !v[j]){
                    dfs(i, j);
                }
            }
        }

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

    }

    private static void dfs(int x, int y) {
        //x, y가 1인 상태
        //y에 연결된 다른 간선 찾아야 함
        v[y] = true;
        res[x][y] = 1;

        for (int i = 0; i < N; i++) {
            if(map[y][i] == 1 && !v[i]){
                //y와 연결된 간선을 시작한 노드와 이어
                dfs(x, i);
            }
        }
    }

}

코드 2 - 플로이드 워셜

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

public class Main {

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

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

        for (int i = 0; i < N; i++) {
            tokens = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(tokens.nextToken());
            }
        }//end input

        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]).append(" ");
            }
            sb.append("\n");
        }
        System.out.print(sb);

    }

}