[백준/Java] 11403 - 경로 찾기

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

문제

---

풀이

이 문제를 접하면서 플로이드-워셜 알고리즘을 처음 알았다

모든 정점에서 모든 정점으로의 경로를 찾는 문제이므로, 플로이드-워셜 알고리즘을 사용하면 매우 간결하게 해결할 수 있다

플로이드-워셜 알고리즘의 핵심 아이디어는

정점 `i`에서 `j`로 가는 경로가 있을 때, 중간에 정점 `k`를 거쳐가는 경로가 있는가? 이다

코드로 표현하면 아주 간단한 3중 for문으로 완성된다

 

물론 dfs나 bfs로도 해결할 수 있다

모든 정점을 시작점으로 순회하면서 각 정점에서 bfs 탐색을 한다

예를 들어 0번 정점에서 탐색을 시작해서 방문하게 되는 모든 정점들(예: 2, 4, 5)은 0번에서 경로가 존재한다는 의미이다

탐색을 마친 후 결과 행렬의 `[0][2]`, `[0][4]`, `[0][5]` 위치에 1을 표시한다

코드

플로이드-워셜 알고리즘 사용

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int[][] arr;

	static int N;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];

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

		for (int[] ints : arr) {
			for (int num : ints) {
				sb.append(num + " ");
			}
			sb.append('\n');
		}

		System.out.println(sb);
		br.close();
	}
}

 

BFS 사용

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int[][] arr;
	static int[][] result;

	static int N;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];
		result = new int[N][N];

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

		for (int i = 0; i < N; i++) {
			bfs(i);
		}

		for (int[] ints : result) {
			for (int num : ints) {
				sb.append(num + " ");
			}
			sb.append('\n');
		}

		System.out.println(sb);
		br.close();
	}

	static void bfs(int node) {
		Queue<Integer> queue = new LinkedList<>();
		boolean[] visited = new boolean[N];
		queue.add(node);

		while (!queue.isEmpty()) {
			int current = queue.poll();

			for (int i = 0; i < N; i++) {
				if (!visited[i] && arr[current][i] == 1) {
					visited[i] = true;
					queue.add(i);
					result[node][i] = 1;
				}
			}
		}
	}
}

결과

제출 번호 98435222 - BFS

제출 번호 98435172 - 플로이드-워셜