[Java] DFS 구현하기 - 재귀 함수 이용 / 인접 리스트 / 배열

ex) 

출처: https://scshim.tistory.com/241

---

                                         Code                                         

import java.io.*;
import java.util.LinkedList;

public class Main {
    static LinkedList<Integer>[] linkedList;
    static boolean[] visit;
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        //정점과 간선 입력&저장
        String str = bf.readLine();
        int n = Integer.parseInt(str.split(" ")[0]);
        int m = Integer.parseInt(str.split(" ")[1]);


        //true, false판별 배열&인접 리스트 생성 및 초기화
        visit = new boolean[n+1];
        linkedList = new LinkedList[n+1];
        for(int i = 0; i < n+1; i++) {
            linkedList[i] = new LinkedList<>();
        }

        //간선의 양 끝 점 u, v입력&저장
        for (int i = 0; i < m; i++) {
            String str2 = bf.readLine();
            int u = Integer.parseInt(str2.split(" ")[0]);
            int v = Integer.parseInt(str2.split(" ")[1]);
            addEdge(u, v);
            addEdge(v, u);
        }

        //true, false판별 및 함수 호출
        for (int i = 1; i < linkedList.length; i++){
            if(!visit[i]) {
                dfs(i);
            }
        }
    }

    //dfs방식 함수
    private static void dfs(int i) {
        visit[i] = true;
        System.out.print(i + " ");
        for (int j : linkedList[i]){
            if (!visit[j])dfs(j);
        }
    }

    //인접 노드 더하기
    private static void addEdge(int u, int v) {
        linkedList[u].add(v);
    }
}

 

---

                                              결과                                                

 

입력

출력