[정리] DFS

DFS

• 하나의 정점으로부터 시작하여 차례대로 모든 정점을 한 번씩 방문하는 알고리즘이다.
• 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽히 탐색한다.
• 자기 자신을 호출하는 순환 알고리즘의 형태이다(재귀함수).

문제와 코드를 통해서 알아보겠다

• 백준 (1260번) DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

풀이

package DFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class DFSBFS {
    static Map<Integer,List<Integer>> map;
    static boolean[] check;
    static StringBuilder sb;
    static void dfs(int v){
        if(check[v-1])
            return;
        sb.append(v+" ");
        check[v-1] = true;
        for(int i : map.get(v)){
            dfs(i);
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());
        check = new boolean[n];
//        map -> key , value -> key:int value : list
        map = new HashMap<>();
        sb = new StringBuilder();
//      초기화
        for(int i = 1;i<=n;i++){
            map.put(i,new ArrayList<>());
        }

        for(int i = 0;i<m;i++){
            st = new StringTokenizer(br.readLine()," ");
            int f = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            map.get(f).add(s);
            map.get(s).add(f);
        }
        for(int i = 1;i<n;i++)
            map.get(i).sort(((o1, o2) -> o1-o2));

/**
 * 5 -> 4, 2
 * 4 -> 5 3
 * 3 -> 4 1
 * 2 -> 5 1
 * 1 -> 2 3
 */
        dfs(v);
        sb.setLength(sb.length()-1);
        System.out.println(sb.toString());
    }
}```