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

문제

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

 

가중치 없는 방향그래프가 주어졌을 때, 모든 정점(i, j)에 대해 i->j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하라. 양수인 경로가 있으면 i행 j열의 숫자를 1로, 없으면 0으로 출력해야 한다.

 

입력:

3

0 1 0

0 0 1

1 0 0

풀이

i행 j열의 값이 1이면 양수인 경로가 있다고 했으므로 입력으로 인접행렬이 주어진 것과 같다.

 

그런데 이 인접행렬은 정점 i에서 j로 바로 가는 경로가 있는가에 대한 정보이다.

i에서 j로 바로 갈 수는 없지만 k를 거쳐서 가는 경로가 존재할 수도 있다. 이 경우를 찾아내야 한다.

 

노드 k는 그래프 상에서 i, j를 제외한 모든 노드가 될 수 있기 때문에 3중 for문을 돌리면서 i -> k -> j가 가능한지 일일이 탐색하자.

i->k1->k2->k3->j 이 경로 확인하려면 3중이 아니라 5중 for문을 돌려야 하는 게 아니냐 할 수 있는데 메모이제이션을 활용하면 3중으로 찾을 수 있다.

하위 경로 (i -> k, k -> j)를 이용해서 상위 경로 (i -> j)를 단계적으로 찾아나가고 있기 때문이다.

즉 i -> k, k -> j가 가능한지 확인할 때 이미 그 하위 경로들을 모두 확인해둔 상태이기 때문에 그냥 메모이제이션한 값들을 가져다 쓰면 된다. (i->k1가 가능했다면 dist[i][k1]이 1일 것이고 k1->k2가 가능했다면 dist[k1][k2]이 1일 것이다.)

 

-> 모든 경로를 탐색하면 무조건 노드 수의 3제곱 O(V^3)의 시간 복잡도를 갖게 되므로 메모이제이션으로 효율을 높이고 있음

-> 탐색하다가 i에서 j로 갈 수 있는 경로를 찾았으면 i행 j열에 저장해두어 나중에 한 번 더 계산하지 않아도 되도록 한다.

코드 설계

• 입력값 받아서 dist 배열 채우기
  • dist배열을 dp배열로 쓸 거임
  • dist[i][j]값이 1이라면 i에서 j로 바로 갈 수 있다는 뜻이므로 1을 채워넣음
  • dist[i][j]값이 0이라면 즉 i에서 j로 바로 갈 수 없다면 이제 어딘가를 거쳐서 갈 수 있는지 확인하면서 최단 경로를 찾아야 함
• 3중 for문을 통해 최단 경로를 구한 후 dist 배열에 업데이트하기
  • 가장 바깥 루프는 k (거쳐야 하는 노드)
  • 안쪽 두 개의 루프는 i, j (시작 노드, 도착 노드)
  • dist[i][k]==1 && dist[k][j]==1 이면 경로가 있다는 뜻이므로 값을 1로 넣어주기

코드

import java.io.*;
import java.util.*;

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

        int n = Integer.parseInt(br.readLine());
        int[][] dist = new int[n][n];

        // 거리 초기화
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                dist[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++) {
                    if(dist[i][k]==1 && dist[k][j]==1)
                        dist[i][j] = 1;
                }
            }
        }

        // 결과 출력
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                System.out.print(dist[i][j] + " ");
            }
            System.out.println();
        }
    }
}