깊이 우선 탐색/DFS 알고리즘이란?

지난 포스팅에서 DFS와 BFS알고리즘을 알아보기 위해 그래프 자료구조를 선행하여 정리했다.

https://hsch19.tistory.com/39

그래프(Graph) 자료구조란 무엇인가?

 

DFS 알고리즘이란?

DFS는 Depth-First  Search의 약자로 깊이 우선 탐색이라고도 불린다.

DFS는 트리나 그래프를 탐색하는 기법 중 하나로, 시작노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘이다.

비유하자면, DFS는 미로 탐색시 한 방향으로 모든 노드를 방문하다가 더 이상 방문할 노드가 없다면 가장 가까운 갈래길로 돌아가 방문하지 않은 노드 방향으로 탐색을 이어가는 것이다.

 

DFS의 특징

• 재귀나 스택을 이용해 자기 자신을 호출하는 형태이다.
• 탐색 시 노드를 방문하면 반드시 방문여부를 체크해야 한다.(이를 검사하지 않으면 무한루프에 빠질 수 있음)
• 그래프에서 간선이나 변수 정보를 수시로 변경해야하는 문제에서 효과적이다.

DFS 과정

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

너비가 아닌 깊이를 우선적으로 탐색했기 때문에 0 - 1 - 2 - 3 - 4라는 경로로 탐색하는 것을 볼 수 있다.

 

DFS의 장점

1. 스택을 사용해서 DFS 구현시 현재 순회중인 노드만 저장하기 때문에 BFS에 비해 메모리 공간을 덜 차지한다.
2. DFS는 목표가 특정 노드 또는 모든 노든에 최대한 빠르게 도달할 때 유용하다.

DFS의 단점

1. DFS를 통해 얻어진 해가 최단 경로라는 보장이 없다.
2. 만약, 답이 아닌 경로가 매우 깊다면 그 경로로 깊이 빠질 수 있다.

기초예제

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

2606번: 바이러스

재귀호출을 사용한 DFS풀이 방법

public class Main {
    static int Node;
    static int Line;
    static int[][] map;
    static boolean[] visited;
    static int count = 0;

    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Node = Integer.parseInt(br.readLine());
        Line = Integer.parseInt(br.readLine());

        map = new int [Node+1][Node+1]; //배열은 0부터 시작하지만 노드는 1부터 시작하기 때문에
        visited = new boolean[Node+1];//착오를 줄이기 위해 0은 버리고 1부터 저장한다.
        count = 0;

        for(int i=0; i<Line; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            map[a][b] = 1; //무방향 그래프는 A-B 와 B-A가 같다.
            map[b][a] = 1;
        }

        dfs(1);
        System.out.println(count-1);

    }//end main

    public static void dfs(int start) {
        visited[start] = true;
        count++;
            for(int i=0; i<=Node; i++) {
                if(map[start][i]==1 && visited[i]!=true) { //간선이 존재하고, 방문하지 않았다면,
                    dfs(i); //재귀호출을 해준다.
                }
            }	
    }//end dfs
	
}//end class

 

 

---

참고자료

https://heytech.tistory.com/55

https://infodon.tistory.com/97

https://developmentnotepad.tistory.com/entry/Algorithm-DFS-BFS

https://olrlobt.tistory.com/35

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html