[11403] 경로 찾기

✔ 경로 찾기

[백준 11403]

문제 분석하기

모든 노드 쌍에 관해 경로가 있는지 여부를 확인해야 하므로 플로이드-워셜 알고리즘을 사용하여 문제에 접근

단, 최단 거리를 구하는 문제가 아니기 때문에 최단 거리를 업데이트하는 부분만 조금 수정 필요

손으로 풀어보기

1. 인접 데이터를 인접 행렬에 저장
2. 변경된 플로이드-워셜 알고리즘을 수행
   • S와 E가 모든 중간 경로 중 1개라도 연결돼 있다면 S와 E는 연결 노드로 저장
3. 알고리즘으로 변경된 인접 행렬을 출력

슈도코드 작성하기

N(인접 행렬의 크기)
distance(노선 데이터를 저장하는 인접 행렬)
for(i -> N만큼 반복하기) {
    for(j -> N만큼 반복하기) {
        인접 행렬 데이터를 distance 행렬에 그대로 저장하기
    }
}
for(k -> N만큼 반복하기) {
    for(i -> N만큼 반복하기) {
        for(j -> N만큼 반복하기) {
            i ~ j 사이에 가능한 모든 경로를 탐색하기
            만약 distance[i][k] == 1이고, distance[k][j] == 1이면 distance[i][j] = 1로 저장
        }
    }
}
distance 배열 출력하기

코드 구현하기

/**
 * 11403) 경로_찾기
 */
public class D062_11403 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // N(인접 행렬의 크기)
        int N = Integer.parseInt(br.readLine());
        // distance(노선 데이터를 저장하는 인접 행렬)
        int distance[][] = new int[N + 1][N + 1];
        // 인접 행렬 데이터를 distance 행렬에 그대로 저장하기
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int v = Integer.parseInt(st.nextToken());
                distance[i][j] = v;
            }
        }
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    // 만약 distance[i][k] == 1이고, distance[k][j] == 1이면
                    if (distance[i][k] == 1 && distance[k][j] == 1)
                        // distance[i][j] = 1로 저장
                        distance[i][j] = 1;
                }
            }
        }
        // distance 배열 출력하기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(distance[i][j] + " ");
            }
            System.out.println();
        }
    }
}