DFS 알고리즘

DFS : Depth First Search

깊이 우선 탐색 알고리즘이다.
즉, 깊이를 쭉 따라가서 탐색하는 것을 우선으로 한다는 의미이다.

그림과 같이, 탐색을 시작할 노드에서부터 연결되어있는 다음 레벨의 노드까지 탐색한다. 그림에서는 루트 노드부터 탐색하는 모양이지만 이는 예시일뿐 꼭 루트부터 탐색해야만 하는 것은 아니다.

그림을 보니 특징이 몇 가지 파악이 된다.

1. 특정 노드에 연결 레벨이 깊으면 깊을수록 탐색이 느리다.

해는 다른 노드에 있는데 쓸데 없이 엉뚱한 깊은 노드를 계속 탐색하는 경우에는 시간이 오래 걸린다.

2. 탐색(또는 방문)했던 노드를 기억해야한다.

그림처럼 5번 노드에서 6번 또는 8번 노드로 탐색을 시작해야 하는데, 6번을 이미 탐색했는지 확인해야 6번으로 갈지 아니면 8번으로 갈지 탐색 경로를 판단할 수 있다.

java로 구현해보면 다음과 같다.

먼저, DFS 그래프 클래스다.

class DfsGraph {
    //노드의 갯수, 방문 여부, 그래프 변수
    private int nodeSize;
    private boolean[] visitArr;
    private int[][] dfsGraph;
    
    public DfsGraph(int nodeSize){
    	//노드 번호를 0이 아닌 1부터 표현하기 위해 갯수보다 하나 더 추가한다.
    	this.nodeSze = nodeSize;
    	this.dfsGraph = new int[nodeSize + 1][nodeSize + 1]
    	this.vidistArr = new boolean[nodeSize + 1]
    }
    
    public int[][] getGraph(){
    	return this.dfsGraph;
    }
    
    public void put(int x, int y){
        //x노드와 y노드를 서로 양방향으로 연결. 연결 여부는 1이라 정의한다.
    	this.dfsGraph[x][y] = this.dfsGraph[y][x] = 1;
    }
    
    public void putSingle(int x, int y){
    	//양방향이 아닌 단방향 노드 연결 함수인데 여기선 쓰이지 않는다.
    	this.dfsGraph[x][y] = 1;
    }
    
    public void printGraph(){
    	for(int i = 0; i < this.dfsGraph.length; i++){
            for(int j = 0; j < this.dfsGraph[i].length; j++){
       		System.out.print(this.dfsGraph[i][j]);
            }
            System.out.println();
        }
    }
    
    public void clearVisitArr(){
    	//탐색여부 초기화이므로 모두 false로 채우기
    	Arrays.fill(this.visitArr, false);
        
        /* 또는
        for(int i = 0; i < this.visitArr.length; i++){
           this.visitArr[i] = false
        }
        */
    }
    
    public void dfs(int vIdx){
    	this.visitArr[vIdx] = true; //일단 탐색 여부 기록
        System.out.print(vIdx + " "); //탐색한 노드를 출력
        
        for(int i = 1; i <= this.nodeSize; i++){
      	    if(dfsGraph[vIdx][i] == 1 && visitArr[vIdx] == false){     
            	dfs(i); //재귀
            }
        }
    }
        
}

다음은 메인(실행) 클래스이다.

public class DfsTestClass {
	public static void main(String args[]){
    	//노드, 엣지 개수
    	int nodeSize = 8
        int edgeSize = 10;
   		
        //DfsGraph 객체 생성
        DfsGraph dfsGraph = new DfsGraph(nodeSize);
        
        //노드 갯수와 엣지 개수 만큼 put 실행
        //노드 갯수는 8이니까 1~8 노드를 엮어주고
        //엣지 개수는 10개니까 put을 10번 콜하면 된다.
        dfsGraph.put(1, 2); //노드1과 2를 엣지로 연결
        dfsGraph.put(1, 3; //노드1과 3을 엣지로 연결
        dfsGraph.put(2, 4) //...
        dfsGraph.put(2, 5);
        dfsGraph.put(3, 6);
        dfsGraph.put(3, 7);
        dfsGraph.put(4, 8);
        dfsGraph.put(5, 8);
        dfsGraph.put(6, 8);
        dfsGraph.put(7, 8);
        
        System.out.println();
        System.out.print("노드 1부터 탐색 : ");
        dfsGraph.dfs(1); //원하는 탐색 시작 노드를 입력
   }
}

(여담이지만 갑자기 로봇청소기가 생각난다.
내가 이미 청소한 경로였는지 확인하고 계속해서 새로운 경로를 찾아가는... )