[JAVA] DFS 리스트 + 재귀 기본 코드

DFS

DFS는 Depth Frist Search의 줄임말로, 깊이 우선 탐색입니다.

그래프 알고리즘에서 BFS와 함께 기본 알고리즘으로 하나의 정점에서 시작해 연결된 모든 정점을 방문할 때, 깊은 정점을 우선 방문하고 더 이상 방문할 정점이 없을 때, 다시 왔던 정점으로 돌아와서 방문하지 않은 정점을 방문하는 식으로 구현이 됩니다. 

아래의 간단한 예시에서 보면, 0 > 1 > 3 을 깊이 우선으로 방문하고 더 이상 방문할 정점이 없으므로, 1로 돌아와 4를 방문하고, 다시 0으로 돌아와 2를 방문하는 식으로 모든 연결된 정점을 방문하고 있습니다. 

0>1>3>4>2 순서로 방문

 

 

JAVA DFS 구현

위의 이미지를 간단하게 DFS 기본 코드를 구현해보면 아래와 같습니다.

ArrayList의 배열과 재귀 함수를 이용하여 구현을 했는데, Edge의 맵을 2차 배열로 구현했을 때 보다 간선(Node)나 정점(Edge)의 수가 많을 경우에도 정상 동작이 가능합니다.

• nodeList는 List<Integer>의 배열로 nodeList[0]은 0에 연결된 정점의 ArrayList ( [1,2] )가 저장됨
• visited 배열은 방문했는 여부를 저장하여 방문한 정점은 재 방문하지 않기 위한 배열로 visited[0]은 0 정점을 방문했는지 여부이고, 그 값이 0이면 미방문 / 1이면 방문
• N과 nodes라는 위의 이미지와 동일한 입력 데이터를 임의로 작성
• 입력받은 간선 정보를 nodeList에 저장 (무방향성인 경우 nodeList[0].add(1) / nodeList[1].add(0) 양방향 모두 저장)
• 0부터 출발한다고 하였을 때, 0을 방문처리(vdisited[0]=1)하고 dfs(0) 함수 실행
• dfs 함수는 현재 정점에서 연결된 방문 가능한 정점을 반복문으로 돌며, 방문을 안 한 정점(if(vdisited[next]==0))이면 방문 처리를 하고 재귀로 dfs 함수를 호출

public class Dfs_cd {
    static List<Integer>[] nodeList;
    static int[] visited;
    public static void main(String[] args) {
        // 입력 데이터
        int N = 5;
        int[][] nodes = {{0,1},{0,2},{1,3},{1,4}};

        // 리스트, 배열 초기화
        nodeList = new ArrayList[N];
        for(int i=0; i<N; i++) nodeList[i] = new ArrayList<>();
        visited = new int[N];

        // 입력받은 간선을 간선 리스트에 저장
        // ex) 1-2 : nodeList[1].add(2); nodeList[2].add(1); 
        // 무방향성이므로 양쪽을 저장 
        for(int[] e : nodes){
            nodeList[e[0]].add(e[1]);
            nodeList[e[1]].add(e[0]);
        }

        visited[0] = 1; // 0부터 출발, 0은 방문 처리
        dfs(0);
    }

    static void dfs(int cur) {
        for(int next : nodeList[cur]) {
            if(visited[next] == 0) { // 이어진 점이 방문한 곳이 아니면
                visited[next] = 1; // 방문 처리하고
                dfs(next); // 해당 점부터 재귀
            }
        }
    }
}