DFS - 깊이 우선 탐색 (Java)

10월 9일 예정인 ICPC 학교 예선을 대회 약 한 달 전인 9월 초중반 즈음에 나가기로 했다...

알고리즘의 알 자도 모르는 나였지만 일단 갖다 박아보는거지!! 라는 마인드로

똑같은 마인드의 팀원들을 구해서 준비를 했다 ㅎㅎㅎ

공부할수록 어렵고 복잡함을 느끼지만 오기도 생기고 재미도 붙어서 올해는 경험삼아 도전해보고, 내년에 제대로 공부하고 해보고 싶어졌다.

 

공부한 것을 정리하기 위해! 포스팅을 한다.

 

---

DFS(깊이 우선 탐색)은 가중치가 없는 그래프에서의 경로를 찾는 방법이다. 왜 깊이 우선이냐면 한 경로를 찍고 끝까지 내려갔다가 돌아오기 때문! 그래서 재귀적으로 움직이는 것이 특징이다.

장점은 구현하기 쉽다! 그리고 저장 공간을 적게 먹고, 목표 노드가 깊게 있다면 그를 빨리 구할 수 있다.

반대로 단점은 해가 없는 경로에 빠지기 쉽고, 찾은 해가 최적의 해라는 보장이 없다는 것?

 

이런 식으로 1-2-3-2-1-4-5 식으로 한 루트의 끝으로 찍었다가 다음 노드로 돌아가는 것!

 

알고리즘을 정렬해보면 :

1. 그래프를 인접 행렬이나 인접 리스트로 구현한다. x-y간 간선이라면 [x][y]=[y][x]=1 꼴로 기입해주자.

2. 방문한 노드를 표시할 boolean 리스트를 구현해준다. 

3. 리스트 기반으로 각 노드에 연결된 다른 노드들을 순차적으로, 재귀적으로 처리하여 방문하지 않은 노드가 없을 때까지 반복한다.

 

코드를 짜봤다.

import java.util.*;

class DFS {
	int nodes, roads;
    boolean[] visited;
    int[][] Graph;
	public DFS(int nodes, int roads){
    	this.nodes = nodes;
        this.roads = roads;
        this.Graph = new int[nodes+1][nodes+1];
        this.visited = new boolean[nodes+1];
        }
    
    public void Graph_set(int x, int y){
    	//그래프를 행렬에 구현
    	Graph[x][y] = Graph[y][x] = 1;
        }
    
    public void dfs(int cur_node){
    	//실행
        visited[cur_node] = true;
        System.out.println(cur_node+"번 노드를 방문합니다.");
        for(int next_node=1; next_node<=nodes; next_node++){
        	if(visited[next_node] == false && Graph[cur_node][next_node] != 0){
            	//재귀 호출
                dfs(next_node);
                }
        }
    }
}

public class Main {
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
        int nodes = sc.nextInt();
        int roads = sc.nextInt();
        int start = sc.nextInt();
        
        //그래프 초기화, 설정
        DFS dfs = new DFS(nodes, roads);
        for(int i=0; i<roads; i++){
        	dfs.Graph_set(sc.nextInt(), sc.nextInt());
        }
        dfs.dfs(start);
        
}
}

이렇게 된다! 처음 보면 되게 복잡해 보이는데, 찬찬히 정렬해보면 그다지 어렵지 않았다. 

다음은 너비우선탐색을 포스팅하겠다.