DFS (깊이우선탐색) 이용한 가능한 모든 경로 구하기

안녕하세요. 오늘은 DFS(깊이우선 탐색)을 이용하여 

"출발점에서 "목적지"까지 도달하는 모든 경로를 구하는 법에 대해 알아보겠습니다.

위의 사진처럼 있을때 1 노드에서 4 노드로 가는 모든 경우의 수는 어떻게 구할까요?

일단 깊이우선 탐색(DFS) 을 구현해보겠습니다.

class DFSAlgorithm{
	private int maps[][] = new int [6][6];		//DFS 인접행렬
	private boolean visit[] = new boolean[6];	//방문했나 안했나 판단할 변수
	
	
	public DFSAlgorithm(){
		//클래스 생성자
		//스택을 초기화하고
		//table 및  visit 변수를 할당 한다.
		
		for(int i=0;i<6;i++){
			for(int j=0;j<6;j++){
				maps[i][j] = 0;
			}
		}
		
		for(int i=0;i<6;i++){
			visit[i] = false;
		}		
	}
	
	public void inputData(int i,int j){
		//데이터를 집어넣는 함수
		//i,j를 넣으면 인접행렬에 값을 넣어준다.
		//무방향 그래프이므로 대칭해서 넣어준다.
		maps[i][j] = 1;
		maps[j][i] = 1;
		
	}
	
	public void DFS(int v){
		//DFS 구현 부분
		visit[v] = true;
		System.out.print(v); //방문노드를 보여주기위한 출력
		for(int i=0;i<6;i++){
			if(maps[v][i]==1 && !visit[i]){
				//노드가 이어져있고 방문을 하지 않았으면
				DFS(i);				
			}			
		}
	}
}

그리고 위에서 보여준 그림의 데이터를 대입해보고 DFS(1) 의 결과를 보겠습니다.

public class test {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		DFSAlgorithm d = new DFSAlgorithm();
		d.inputData(1, 2);
		d.inputData(1, 3);
		d.inputData(2, 3);
		d.inputData(2, 5);
		d.inputData(3, 4);
		d.inputData(3, 5);
		d.inputData(4, 5);
		
		d.DFS(1);
	}
 
}

 

네 위와 같이 1 2 3 4 5 순으로 방문하였습니다.

하지만 저희가 구해야 할 것은 1부터 4까지 가는 모든 경로이기 때문에 DFS(int v) 코드를 아래와 같이 수정해야 합니다.

 

public void DFS(int v, int goal){ 
//v :출발노드 goal:도착노드

출발노드 v와 도착노드 goal을 인자로 받습니다.

경로를 받기 위해 stack도 추가해야하는데요

클래스 변수에 stack을 추가해줍시다.

Stack<Integer> stack;

그리고 생성자에서도 stack을 초기화 해줍시다!

stack = new Stack();

자 이제 준비는 끝났습니다.

DFS 구현부분을 아래와 같이 바꿔보았습니다.

public void DFS(int v,int goal){
		//DFS 구현 부분
		visit[v] = true;
		stack.push(v); //스택에 값을 넣어준다.
		
		if(v == goal){ //목표노드에 왔으면
			
			//// 스택값 출력
			int count=stack.size(); //스택의 크기를 받을 변수 
			for(int i=0; i<count;i++){
				System.out.print(stack.elementAt(i)+" ");
			}
			System.out.println("출력완료");
			//// 스택값 출력
			
			stack.pop(); //DFS에서 빠져나올땐  pop을 합니다. 
			return; 
		}
	
		
		for(int i=0;i<6;i++){
			if(maps[v][i]==1 && !visit[i]){
				//노드가 이어져있고 방문을 하지 않았으면
				DFS(i,goal);	
				visit[i]=false; //DFS에서 빠져나오면 해당노드는 방문하지 않은 것으로 한다. 
			}			
		}
		
		stack.pop(); //DFS에서 빠져나올땐 pop을 합니다. 
		
	}

중요한 부분은 아래 부분 입니다.

for(int i=0;i<6;i++){
	if(maps[v][i]==1 && !visit[i]){
		//노드가 이어져있고 방문을 하지 않았으면
		DFS(i,goal);	
		visit[i]=false; //DFS에서 빠져나오면 해당노드는 방문하지 않은 것으로 한다. 
	}			
}

visit[i] = false; 를 함으로써 DFS의 다른 모든 경로도 구할 수 있게 되었습니다.

위와 같이 했을 경우 실행 결과입니다.

이것으로 DFS알고리즘을 이용하여 모든 경로를 구하는 법에 대해 알아보았습니다^^

감사합니다.