[백준] 11403번: 경로 찾기(dfs, bfs)

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

11403번: 경로 찾기

dfs 코드

import java.util.Scanner;

public class Main {
	static int[][] graph;	// 방향그래프 인접 행렬
	static int[][] path;	// 결과 출력할 2차원 배열
	static boolean[] visit;	// 탐색 여부 체크
	static int N;			// 정점의 갯수

	public static void dfs(int x, int y) {
		visit[y] = true;	// 각 행마다 열을 기준으로 체크하므로 y값 체크
		path[x][y] = 1;		// x -> y로 이동하는 경로 존재, 1로 설정

		for(int i=0; i<N; i++) {
			if(graph[y][i] == 1 && visit[i] == false) {
				dfs(x, i);
			}
		}
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		graph = new int[N][N];
		path = new int[N][N];
		visit = new boolean[N];

		// 그래프의 인접 행렬
		// i => j 간선이 존재하면 1, 존재하지 않으면 0
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				graph[i][j] = scan.nextInt();
			}
		}

		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				visit[j] = false;	// 행(i) 마다 경로를 탐색해야 하므로 방문한곳 초기화
			}

			for(int j=0; j<N; j++) {
				if(graph[i][j] == 1 && visit[j] == false) {
					dfs(i, j);
				}
			}
		}

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

 

bfs 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int[][] graph;	// 그래프 인접 행렬
	static int[][] result;	// 결과 출력할 배열
	static boolean[] visit;	// 탐색 여부 체크
	static int N;			// 정점의 갯수

	public static void bfs(int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(start);	
		
		while(!q.isEmpty()) {
			int temp = q.poll();	// 첫번째 방문한 위치 빼준다.
			for(int i=0; i<N; i++) {
				if(graph[temp][i] == 1 && visit[i] == false) { 
					q.offer(i);
					visit[i] = true;	// 방문한곳 - 다시 방문X, true로 체크
					/*
					 * 예제 입력을 보면,
					 *      0 1 0
					 *      0 0 1
					 *      1 0 0
					 * 0은 1로 연결, 1은 2로 연결, 2는 0으로 연결되어 있음
					 * 최종적으로 0은 1, 2, 다시 0으로 돌아올 수 있음
					 */
					result[start][i] = 1;	// 경로존재할 시 1로 변경.	
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		graph = new int[N][N];
		result = new int[N][N];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				graph[i][j] = scan.nextInt();
			}
		}
		
		for(int i=0; i<N; i++) {
			visit = new boolean[N];
			bfs(i);
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				System.out.print(result[i][j] + " ");
			}
			System.out.println();
		}
		scan.close();
	}

}

풀이

노드를 탐색할때마다, 경로가 존재할때 1로 설정한다.

기존의 dfs와 동일하게 i -> j로 갈수있는 경로가 있고, 방문하지 않은경우 dfs를 호출한다.

dfs에서는 호출받은 i, j 좌표는 방문할수 있는 곳이므로 방문체크를 하고, 출력할 배열 path[][]에 1로 설정한다.

 

사실 아직 dfs, bfs, 그래프에 대한 이해가 완벽치 않아서 구현도 어려웠고... 블로그를 수십개는 본것같다 ㅠㅠ

하나하나 논리를 그려가며 이해해보도록 노력해야겠다 ...