[Java] DFS로 모든 이동 경로 구하기

DFS를 이용해 출발지(시작 정점)에서 목적지(도착 정점)까지의 모든 경로를 구해보자.

 

DFS에 대해 자세히 알고 싶다면 아래 포스트 참고

 

[Java] DFS 깊이 우선 탐색 - 인접 리스트 / 인접 행렬로 구현

더보기) 인접 행렬을 이용해 그래프를 구성한 기존의 DFS 구현 코드

import java.util.*;

public class DFS {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt(); // 정점의 개수 
		int m = sc.nextInt(); // 간선의 개수 
		int v = sc.nextInt(); // 탐색을 시작할 정점의 번호 
		boolean visited[] = new boolean[n + 1]; 
		int[][] adjArray = new int[n+1][n+1];

		for(int i = 0; i < m; i++) {
			int v1 = sc.nextInt();
			int v2 = sc.nextInt();

			adjArray[v1][v2] = 1;
			adjArray[v2][v1] = 1;
		}

		dfs(v, adjArray, visited);
	}

	public static void dfs(int v, int[][] adjArray, boolean[] visited) {
		visited[v] = true;
		System.out.print(v + " ");

		for(int i = 1; i <= adjArray.length-1; i++) {
			if(adjArray[v][i] == 1 && !visited[i]) {
				dfs(i, adjArray, visited);
			}
		}
	}

}

입력

4 5 1
1 2
1 3
1 4
2 4
3 4

출력

1 2 4 3 

 

구현

출발지와 목적지까지의 모든 경로를 나타내기 위해 기존의 DFS 코드에서처럼 탐색을 시작할 정점의 번호 v만 입력받는 것이 아니라 

탐색을 끝낼 정점의 번호 end값도 추가로 입력받는다.

 

그리고 경로를 받기 위해 stack을 추가한다.

 

Scanner sc = new Scanner(System.in);

int n = sc.nextInt(); // 정점의 개수 
int m = sc.nextInt(); // 간선의 개수 
int v = sc.nextInt(); // 탐색을 시작할 정점의 번호 (출발지)
int end = sc.nextInt(); // 탐색을 끝낼 정점의 번호 (목적지)

Stack<Integer> stack = new Stack<>(); // 경로를 받기 위한 스택 

boolean visited[] = new boolean[n + 1]; 
int[][] adjArray = new int[n+1][n+1];

for(int i = 0; i < m; i++) {
	int v1 = sc.nextInt();
	int v2 = sc.nextInt();

	adjArray[v1][v2] = 1;
	adjArray[v2][v1] = 1;
}

dfs_allPath(v, end, stack, adjArray, visited);

 

DFS 함수를 수행하면서 stack에 출발지에서 목적지까지 거쳐갔던 모든 노드들이 저장된다.

 

1. 처음 DFS 함수를 호출하게 되면 int v에 탐색을 시작할 정점의 번호가 들어있고, 이 시작 정점부터 DFS 탐색을 한다.

정점을 방문하면 visited[v]에 true 값을 넣어 방문했다고 표시한다.

그리고 경로를 확인하기 위해 스택에도 방문한 정점의 값을 넣는다.

 

2. 현재 정점과 인접한 정점들을 찾기 위해 모든 정점을 for문을 이용해 돌며 인접 정점을 탐색한다.

현재 정점과 간선으로 연결되어 있고(인접하고), 아직 방문하지 않은 visited가 false인 정점을 찾는다.

인접한 정점을 찾았다면 다시 그 정점부터 다시 DFS를 수행한다.

 

3. 기존의 DFS 코드는 더 이상 방문하지 않은 정점이 없을 때까지 탐색을 한다.

하지만 지금은 모든 경로를 찾아야 하기 때문에 dfs후에 visited[i]의 값을 false로 바꾸어 해당 노드를 방문하지 않은 것으로 만들어준다.

그래야지 한 경로를 찾고 끝나는 것이 아니라, 다른 모든 경로를 구할 수 있다.

 

4.

그리고 현재 정점이 end 목적지 번호와 같은 순간이 바로 목표 노드에 왔다는 의미이므로

이때 스택에 저장된 구해진 모든 경로를 출력하면 되는 것이다.

 

5.

마지막으로 dfs를 빠져나올 땐 pop()로 스택에 저장된 값을 없애준다.

 

public static void dfs_allPath(int v, int end, Stack<Integer> stack, int[][] adjArray, boolean[] visited) {
	// 1
	visited[v] = true;
	stack.push(v); // 스택에 값을 넣어줌
	
	// 4
	if(v == end) { //목표 노드에 왔다면
		for(int i = 0; i < stack.size(); i++) { // 스택 값 출력 - 경로 출력 
			System.out.print(stack.elementAt(i) + " ");
		}
		System.out.println();
	}

	// 2
	for(int i = 1; i <= adjArray.length-1; i++) {
		if(adjArray[v][i] == 1 && !visited[i]) {
			dfs_allPath(i, end, stack, adjArray, visited);
            
			// 3. dfs 후에 방문 노드를 false로 만들어주어 해당 노드를 방문하지 않은 것으로 해줌 
			// -> 모든 경로를 구하기 위함 
			visited[i] = false; 
		}
	}
	
	// 5
	stack.pop(); //dfs 빠져 나올땐 pop()
}

전체 코드

import java.util.*;

public class DFS_AllPath {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt(); // 정점의 개수 
		int m = sc.nextInt(); // 간선의 개수 
		int v = sc.nextInt(); // 탐색을 시작할 정점의 번호 (출발지)
		int end = sc.nextInt(); // 탐색을 끝낼 정점의 번호 (목적지)
		
		Stack<Integer> stack = new Stack<>(); // 경로를 받기 위한 스택 
		
		boolean visited[] = new boolean[n + 1]; 
		int[][] adjArray = new int[n+1][n+1];

		for(int i = 0; i < m; i++) {
			int v1 = sc.nextInt();
			int v2 = sc.nextInt();

			adjArray[v1][v2] = 1;
			adjArray[v2][v1] = 1;
		}

		dfs_allPath(v, end, stack, adjArray, visited);
	}

	public static void dfs_allPath(int v, int end, Stack<Integer> stack, int[][] adjArray, boolean[] visited) {
		visited[v] = true;
		
		stack.push(v); // 스택에 값을 넣어줌
		
		if(v == end) { // 목표 노드에 왔다면
			for(int i = 0; i < stack.size(); i++) { // 스택 값 출력 - 경로 출력 
				System.out.print(stack.elementAt(i) + " ");
			}
			System.out.println();
		}

		for(int i = 1; i <= adjArray.length-1; i++) {
			if(adjArray[v][i] == 1 && !visited[i]) {
				dfs_allPath(i, end, stack, adjArray, visited);
				
				// dfs 후에 방문 노드를 false로 만들어주어 해당 노드를 방문하지 않은 것으로 해줌
				// -> 모든 경로를 구하기 위함 
				visited[i] = false; 
			}
		}
		
		stack.pop(); //dfs 빠져 나올땐 pop()
	}

}

입력

 

4 5 1 3
1 2
1 3
1 4
2 4
3 4

출력

1 2 4 3 
1 3 
1 4 3