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

문제

✔ 난이도 - Silver 1

플로이드–워셜 알고리즘 사용 풀이

기존

설명

인접행렬에서 1인 좌표를 graph에 저장(방향0)
(0,0) ~ (N-1,N-1) 까지 돌면서 i->j 길이 있는지 graph를 통해서 확인

• 매 좌표 검사할때마다 stack, visited, answer 초기화해줘야 함
• i번째줄의 i는 항상 0 이다. 0->0, 1->1 이런거는 바로 길이 있는게 아니라 무조건 다른 좌표를 통해 돌아서 가야한다는 뜻
  • 따라서 첫 시작 i는 visited했다고 바꾸지 x
• stack에서 꺼낸 node값이 찾는 j값과 같으면 길이 있는 것 + 해당 node가 visited여야 함

이 풀이는 $N^2$번의 DFS를 돌리고 있는데, $N$번의 DFS만으로도 해결이 가능하다.
(하단의 개선 풀이 참고)

풀이

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer>[] graph = new ArrayList[N];
        for (int i = 0; i < N; i++){
            graph[i] = new ArrayList<>();
        }

        StringTokenizer st;
        for (int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++){
                int num = Integer.parseInt(st.nextToken());
                if (num == 1) {
                    graph[i].add(j);
                }
            }
        }
        // System.out.println(Arrays.toString(graph));

        Stack<Integer> stack;
        boolean[] visited;
        int answer = 0;
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                stack = new Stack<>();
                visited = new boolean[N];
                answer = 0;

                stack.push(i);
                // visited[i] = true;

                while (!stack.isEmpty()) {

                    int node = stack.pop();
                    if (node == j && visited[node] == true){
                        answer = 1;
                        break;
                    }
                    
                    for (int n : graph[node]) {
                        if (visited[n] == false) {
                            stack.push(n);
                            visited[n] = true;
                        }
                    }

                }
                sb.append(answer).append(" ");
            }

            sb.append("\n");
        }

        
        System.out.println(sb);
    }
}

개선

설명

알고리즘 문제에서는 이미 구한 정보를 어떻게 재활용할까(여기서는 한 번의 DFS로 모든 j 확인하기)를 고민하자

출발점 i가 정해지면, 한 번의 DFS만으로도 i에서 갈 수 있는 모든 노드를 다 알아낼 수 있다.
위의 방식처럼 j를 하나하나 바꿔가며 DFS를 새로 시작하지 않아도 됨

• for i (출발 노드 $0 \sim N-1$)
  • visited 배열과 stack 초기화
  • DFS 실행: i에서 갈 수 있는 모든 노드를 방문하여 visited를 true로 바꿈
  • 결과 출력: visited 배열을 쭉 보면서 true면 1, false면 0을 출력.

풀이

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer>[] graph = new ArrayList[N];
        for (int i = 0; i < N; i++){
            graph[i] = new ArrayList<>();
        }

        StringTokenizer st;
        for (int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++){
                int num = Integer.parseInt(st.nextToken());
                if (num == 1) {
                    graph[i].add(j);
                }
            }
        }
        // System.out.println(Arrays.toString(graph));

        Stack<Integer> stack = new Stack<>();
        boolean[][] visited = new boolean[N][N];;
        for (int i = 0; i < N; i++){
        	stack.clear();
            stack.push(i);
            while (!stack.isEmpty()){
                int node = stack.pop();
                for (int n : graph[node]){
                    if (visited[i][n] == false){
                        stack.push(n);
                        visited[i][n] = true;
                    }
                }
            }
        }

        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                sb.append(visited[i][j] ? "1 " : "0 ");
            }
            sb.append("\n");
        }

        
        System.out.println(sb);
    }
}

⏰ 시간복잡도

주어진 조건($N \leq 100$)을 기준으로 두 코드의 시간 복잡도를 계산해 보면, 왜 두 번째 방식이 안전한지 수치로 확인할 수 있다.

그래프에서 간선의 개수 $M$은 최대 $N^2$(모든 노드가 서로 연결된 경우)이 될 수 있다는 점을 기억하고 진행

1. 기존 코드 (비효율적): $O(N^4)$

• 구조: 출발지($N$) $\times$ 도착지($N$) $\times$ DFS 탐색($N+M \approx N^2$)
• 계산: $N \times N \times N^2 = N^4$
• $N=100$일 때 연산 횟수: $100^4 = \mathbf{100,000,000}$ (1억 번)
• 평가: 보통 Java에서 1초에 1억 번의 연산을 기준으로 잡는다. $N$이 딱 100일 때는 아슬아슬하게 통과하거나, 서버 상태에 따라 시간 초과가 날 수 있음

2. 개선 코드 (효율적): $O(N^3)$

• 구조: 출발지($N$) $\times$ DFS 탐색($N+M \approx N^2$)
• 계산: $N \times N^2 = N^3$
• $N=100$일 때 연산 횟수: $100^3 = \mathbf{1,000,000}$ (100만 번)
• 평가: 100만 번은 컴퓨터에게 매우 가벼운 연산 -> 0.01초 내외로 아주 빠르게 통과

구분	시간 복잡도	실제 연산 횟수 (최악의 경우)	여유도
이전 코드	$O(N^4)$	100,000,000	위험
고친 코드	$O(N^3)$	1,000,000	매우 안전 (100배 빠름)

💡 왜 $N^3$인가?

인접 행렬 문제에서 간선의 개수 $M$은 최대 $N^2$

1. 인접 리스트를 사용한 DFS의 복잡도는 $O(N + M)$
2. 이 문제에서는 $M$이 $N^2$이 될 수 있으므로, 한 번의 DFS는 $O(N^2)$
3. 이 DFS를 $N$번 반복하므로 최종적으로 $O(N \times N^2) = O(N^3)$

이 문제의 정석 풀이 중 하나인 '플로이드-워셜(Floyd-Warshall)' 알고리즘도 시간 복잡도가 $O(N^3)$

플로이드-워셜 vs DFS/BFS

• 플로이드-워셜: $N$이 500 이하로 작을 때. 코드가 짧아야 할 때. 모든 지점 간의 관계를 다 알아야 할 때
• DFS/BFS: $N$이 크거나(1,000 이상), 특정 출발점에서 시작하는 경로만 궁금할 때.

"모든 지점 사이의 최단 거리를 구해라" 같은 문제에 대해서는 플로이드-워셜이 좋음