문제
N개의 정점으로 이루어진 가중치 없는 방향 그래프가 인접 행렬로 주어질 때, 임의의 두 정점 i, j 사이에 경로(직접 간선 또는 중간 경유 포함)가 존재하는지 여부를 모든 쌍에 대해 구하는 문제다. N이 최대 100으로 작으므로 플로이드-워셜 알고리즘을 경로 존재 여부에 적용하면 O(N^3)으로 충분히 해결된다.
입력
- 첫째 줄: 정점 수 N (1 이상 100 이하)
- 이후 N개 줄: N×N 인접 행렬 (1이면 간선 존재)
출력
N×N 행렬을 출력한다. i→j 경로가 존재하면 1, 없으면 0.
예제
| 입력 | 출력 |
|---|---|
3 0 1 0 0 0 1 1 0 0 | 1 1 1 1 1 1 1 1 1 |
풀이
플로이드-워셜의 점화식 map[i][j] = map[i][j] || (map[i][k] && map[k][j])를 적용하여 도달 가능성 행렬을 완성한다.
- N×N 인접 행렬 입력
- 중간 경유 노드 k를 0부터 N-1까지 순회
- 모든 (i, j) 쌍에 대해 k를 거쳐 갈 수 있으면
map[i][j] = 1로 갱신 - 최종 행렬 출력
핵심 아이디어: 플로이드-워셜의 점화식에서 거리 대신 도달 가능 여부(boolean)를 저장하면, 모든 쌍의 전이적 연결성(Transitive Closure)을 O(N^3)에 계산할 수 있다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day127BOJ11403경로찾기플로이드와샬 { // 11403 경로찾기 플로이드 와샬
static int N;
static int[][] map;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int i = 0; i < N; i++) {
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 < N; i++) {
for (int j = 0; j < N; j++)
sb.append(map[i][j]).append(" ");
sb.append("\n");
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(V³)
- 공간: O(V²)