백준 11403 경로 찾기 JAVA

문제

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

---

입출력

---

예제

---

태그

• 그래프 이론
• 그래프 탐색
• 플로이드–워셜

---

풀이

• 플로이드-워셜 알고리즘을 사용한다.
• N이 100이하이므로 100 X 100 X 100을 해도 1억 미만이므로 사용 가능
• k는 중간지점
• i->k, k->j가 모두 1이면 i->j 또한 갈 수 있으므로 1로 값을 저장한다.

---

코드

정답 코드

/**
 * 11403_경로 찾기
 *
 * 플로이드-워셜 알고리즘을 사용한다.
 * N이 100이하이므로 100 * 100 * 100을 해도 1억 미만이므로 사용 가능
 * k는 중간지점
 * i->k, k->j가 모두 1이면 i->j 또한 갈 수 있으므로 1로 값을 저장한다.
 */

public class P_11403 {
    static int N;
    static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                map[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 (map[i][k] == 1 && map[k][j] == 1) {
                        map[i][j] = 1;
                    }
                }
            }
        }

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println("");
        }
    }
}