[백준] 11403번 - 경로 찾기

 

 

이 문제는 간단하게 bfs를 이용한 탐색을 통해 풀었다. 이미 지나가지 않은 점이고 간선이 존재하는 경우 탐색을 진행했고, 탐색을 하면서 갈 수 있는 경로의 값들을 갱신해주는 방식으로 문제를 해결할 수 있다.

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

public class p11403 {
	public static int a;
	public static int[][] ary;
	public static boolean[] visited;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		a = Integer.parseInt(br.readLine());
		ary = new int[a + 1][a + 1];

		for (int i = 1; i <= a; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= a; j++) {
				ary[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for (int i = 1; i <= a; i++) {
			visited = new boolean[a + 1];

			for (int j = 1; j <= a; j++) {
				if (visited[j] == false && ary[i][j] == 1) {
					bfs(i, j);
				}
			}
		}

		for (int i = 1; i <= a; i++) {
			for (int j = 1; j <= a; j++) {
				System.out.print(ary[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void bfs(int start, int end) {
		Queue<Integer> q = new LinkedList<>();
		q.add(end);

		while (!q.isEmpty()) {
			int n = q.poll();

			for (int i = 1; i <= a; i++) {
				if (visited[i] == false && ary[n][i] == 1) {
					q.add(i);
					visited[i] = true;
					ary[start][i] = 1;
				}
			}
		}
	}
}

 

 

이 문제는 탐색문제로 풀 수도 있지만 플로이드 와샬 알고리즘을 이용하여서도 풀이가 가능하다.

플로이드 와샬 알고리즘을 간단하게 설명하면 i에서 j로 이동할 때 중간지점이 k를 거쳐 i->k->j 가 가능한지를 판단하는 문제이다. 이 문제에선 그렇지 않았지만 만약에 간선들 끼리의 가중치가 있다면 i->j의 값과 i->k->j의 값을 비교해 더 효율적인 방법으로 문제를 해결하도록 한다. 이 문제에서는 가중치가 존재하지 않았기 때문에 거쳐가는 정점을 가지고 판단할 수 있었다.

플로이드 와샬 알고리즘에 간단한 예제 코드는 아래 링크를 참고하면 된다.

https://ddamdoo.tistory.com/199

FloydWashall 알고리즘

 

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

public class p11403fw {
	public static int a;
	public static int[][] ary;
	public static boolean[] visited;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		a = Integer.parseInt(br.readLine());
		ary = new int[a + 1][a + 1];

		for (int i = 1; i <= a; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= a; j++) {
				ary[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for (int k = 1; k <= a; k++) {
			for (int i = 1; i <= a; i++) {
				for (int j = 1; j <= a; j++) {
					if (ary[i][k] == 1 && ary[k][j] == 1) {
                    // i에서 k를 거쳐 j로 갈 수 있는지 유무
						ary[i][j] = 1;
					}
				}
			}
		}

		for (int i = 1; i <= a; i++) {
			for (int j = 1; j <= a; j++) {
				System.out.print(ary[i][j] + " ");
			}
			System.out.println();
		}
	}
}