[백준 11403] 경로 찾기 - 자바

 

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

11403번: 경로 찾기

1. 풀이

---

모든 정점에 대해서 i에서 j로 가는 경로를 찾는 것이 힌트라고 생각합니다.

 

그러므로 모든 정점에 대해서 dfs나 bfs중 하나를 선택하여 i에서 j로 가는 간선이 존재하는 곳에 1로 표시하면 됩니다.

 

즉, 각 정점에서 dfs나 bfs로 탐색을 진행합니다.

 

2. 코드

---

2.1 dfs

import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in); 
		
		int num = sc.nextInt();
		
		int[][] graph = new int[num][num];
		int[][] result = new int[num][num];
		
		// 입력
		for(int i = 0; i < num; i++) {
			for(int j = 0; j < num; j++) {
				graph[i][j] = sc.nextInt();
			}
		}
		
		Queue<Integer> queue;
		boolean[] visited;
		
		for(int i = 0; i < num; i++) { // 각 정점마다 탐색을 진행.
			// 아래부터는 dfs 탐색.
			queue = new LinkedList<Integer>();
			visited = new boolean[num];
			queue.offer(i);
			
			int tmp;
			while(!queue.isEmpty()) {
				tmp = queue.poll();
				for(int j = 0; j < num; j++) {
					if(graph[tmp][j] == 1 && visited[j] != true) {
						queue.offer(j);
						visited[j] = true;
						result[i][j] = 1; // 만약 i번째 정점에서 j를 거친다면 1을 표시.
					}
				}
			}
		}
		
		// 출력
		for(int i = 0; i < num; i++) {
			for(int j = 0; j < num ; j++)
				System.out.print(result[i][j]+" ");
			System.out.println();
		}
		
		sc.close();
		return;
	}
}

 

2.2 bfs

import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in); 
		
		int num = sc.nextInt();
		
		int[][] graph = new int[num][num];
		int[][] result = new int[num][num];
		
		for(int i = 0; i < num; i++) {
			for(int j = 0; j < num; j++) {
				graph[i][j] = sc.nextInt();
			}
		}
		
		Queue<Integer> queue;
		boolean[] visited;
		
		for(int i = 0; i <num; i++) { // 각 정점마다 탐색을 진행.
			// 아래부터는 bfs 탐색.
			queue = new LinkedList<Integer>();
			visited = new boolean[num];
			queue.offer(i);
			int tmp;
			while(!queue.isEmpty()) {
				tmp = queue.poll();
				for(int j = 0; j < num; j++) {
					if(graph[tmp][j] == 1 && visited[j] != true) {
						visited[j] = true;
						queue.offer(j);
						result[i][j] = 1; // 만약 i번째 정점에서 j를 거친다면 1.
					}
				}
			}
		}
		
		for(int i = 0; i < num; i++) {
			for(int j = 0; j < num ; j++)
				System.out.print(result[i][j]+" ");
			System.out.println();
		}
		
		sc.close();
		return;
	}
}