[BOJ/JAVA] 11403번: 경로 찾기

11403번: 경로 찾기

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

키워드

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램

---

구현

• 단순 플로이드-워셜 알고리즘을 이용하여 구현한다.

private static void floydWarshall()

k를 경유하여 i에서 j로 갈 수 있으면 경로에 추가한다.

---

코드

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

public class java_11403 {
    static int N;

    static int board[][];

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

        N = Integer.parseInt(br.readLine());

        board = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        floydWarshall();

        printBoard();

        br.close();
    }

    private static void printBoard() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static void floydWarshall() {
        // k를 경유하여
        for (int k = 0; k < N; k++) {
            // i에서
            for (int i = 0; i < N; i++) {
                // j를 갈 수 있는가?
                for (int j = 0; j < N; j++) {
                    // i->j 바로 갈 수 있으면 스킵
                    if (board[i][k] == 1 && board[k][j] == 1) {
                        board[i][j] = 1;
                    }

                }
            }
        }
    }
}

---

Uploaded by N2T