[DFS] 경로찾기(Find Directions)

BackJoon 

#11403 - 경로찾기(Find Directions)

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

위 문제는 DFS 탐색 예제입니다...

DFS는 보통 재귀함수 (Recursion)을 사용하는데, 재귀함수에 대한 연습도 할 겸 풀어보시면 좋습니다.

우선 기본적으로 DFS 재귀함수를 통해 i에서 j로가는 경로가 있는지 c 1차원 배열에 경로 여부를 체크합니다. 또한, 다음 경로탐색을 위해 Arrays.fill 메서드를 이용 0으로 초기화 해줍니다.

n+1로 n값에 +1을 한 이유는 편의상 배열의 첨자와 정점의 싱크를 맞추기 위해서 입니다. 0번 인덱스는 신경쓰지 않으셔도 됩니다. 즉 정점은 1부터 시작하니 그냥 2차원배열이든 1차원배열이든 1첨자로 부터 시작하기 위해 n+1크기로 할당한 것입니다.

보통 재귀함수를 하면 무한 루프에 빠지지 않기 위해 초기 분기처리를 하지만, dfs 재귀는 다음 갈 정점을 방문했는지 여부를 따지기 때문에 따로 처리할 필요가 없습니다...

흠...생각보다 별 게 없네요... 아 그리고 해당 문제는 무 방향 그래프가 아닌 방향 그래프란 점은 문제를 파악하시면, 자연스럽게 알 수 있습니다. 아래는 해당 코드입니다.

package BackJoon.Graph.DFS;

import java.util.Arrays;
import java.util.Scanner;

public class FindDirections {

	static int[][] a; // 인접행렬로 이루어진 방향그래프
	static int[] c; //check 방문 여부 저장하는 1차원 배열
	static int[][] path; //i,j로 가는길 여부를 저장하는 2차원 배열
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		a = new int[n+1][n+1];
		c = new int[n+1];
		path = new int[n+1][n+1];
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				a[i][j] = sc.nextInt();
			}
		}
		
		
		for(int i=1; i<=n; i++){
			dfs(i);
			
			for(int j=1; j<=n; j++){
				path[i][j] = c[j];
			}
			//다음 탐색을 위해 리셋
			Arrays.fill(c, 0);
		}
		
		
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				System.out.print(path[i][j]+" ");
			}
			System.out.println();
		}


	}
	private static void dfs(int v) {
		int n = a.length-1;
		
		for(int i=1; i<=n; i++){
			
			//v->i갈 수있는 길이 있고, 방문하지 않은 경우
			if(a[v][i]==1 && c[i]==0){
				c[i] = 1; // 방문체크
				dfs(i);
			}
		}
		
		
	}

}