DFS 기본 코드 인접 배열 방식, 인접 리스트 방식

빈출도가 높은 DFS( Depth First Search) 방식을 배열과 리스트로 방식으로 각각 알아보자

-> 리스트 방식을 더 권장

 

1. 배열 방식

//      1  2  3  4
//
// 1    0  1  1  0
// 2    1  0  0  1
// 3    1  0  0  1
// 4    0  1  1  0
// 위에 처럼 배열로 푸는 방식
public class DFS기본코드배열 {
    static int edge; // 간선의 수  4
    static int vertex; // 정점의 수  4
    static int[][] map; // 정점 간의 연결의 정보를 담는 객체
    static boolean[] visited; // 정점 방문 체크를 위한 객체
    public static void main(String[] args) {
        // [vertex + 1] 을 하는 것은 0 번째 인덱스를 사용하지 않으려고 1부터 사용하려고
        Scanner sc = new Scanner(System.in);
        vertex = sc.nextInt();
        edge = sc.nextInt();
        map = new int[vertex + 1][vertex + 1];
        visited = new boolean[vertex + 1];

        for(int i = 0; i < edge; i++){
            int start = sc.nextInt();
            int next = sc.nextInt();

            map[start][next] = 1; //  1번과 4번이 연결되어 있다하면 map[1][4]를 1로 만든 것
            map[next][start] = 1; // 반대로 map[4][1]도 1이 되어야함 ->하지만 방향이 정해져 있으면 이건 안씀
        }

        dfs(1);


    }

    private static void dfs(int start) {
        visited[start] = true; // 1 2 3
        System.out.println(start + " ");

        for(int i = 1; i <vertex + 1; i++){
            if(map[start][i] == 1 && visited[i] == false){
                dfs(i);
            }
        }
    }
}

 

 

• 1번 정점은 2번과 3번 정점과 연결됨 (map[1][2] = 1, map[1][3] = 1)
• 2번 정점은 1번과 4번 정점과 연결됨 (map[2][1] = 1, map[2][4] = 1)
• 3번 정점은 1번과 4번 정점과 연결됨 (map[3][1] = 1, map[3][4] = 1)
• 4번 정점은 2번과 3번 정점과 연결됨 (map[4][2] = 1, map[4][3] = 1)

DFS 탐색 과정

초기 호출: dfs(1)
현재 visited[] 배열: [false, false, false, false, false]

1. dfs(1) 호출:
   • visited[1]를 true로 설정하고 1을 출력.
   • visited[] 상태: [false, true, false, false, false]
   • 1번 정점과 연결된 정점 탐색:
     • map[1][2] = 1이므로 dfs(2) 호출.
2. dfs(2) 호출:
   • visited[2]를 true로 설정하고 2를 출력.
   • visited[] 상태: [false, true, true, false, false]
   • 2번 정점과 연결된 정점 탐색:
     • map[2][1] = 1이지만, visited[1] = true이므로 탐색하지 않음.
     • map[2][4] = 1이므로 dfs(4) 호출.
3. dfs(4) 호출:
   • visited[4]를 true로 설정하고 4를 출력.
   • visited[] 상태: [false, true, true, false, true]
   • 4번 정점과 연결된 정점 탐색:
     • map[4][2] = 1이지만, visited[2] = true이므로 탐색하지 않음.
     • map[4][3] = 1이므로 dfs(3) 호출.
4. dfs(3) 호출:
   • visited[3]를 true로 설정하고 3을 출력.
   • visited[] 상태: [false, true, true, true, true]
   • 3번 정점과 연결된 정점 탐색:
     • map[3][1] = 1이지만, visited[1] = true이므로 탐색하지 않음.
     • map[3][4] = 1이지만, visited[4] = true이므로 탐색하지 않음.

모든 연결된 정점이 탐색되었으므로 탐색이 종료됩니다.

탐색 순서 출력

1 2 4 3

 

 

 

2.  인접 리스트 방식

 

// 인접 리스트 방식
// 1:     2   3
// 2:     1   4
// 3:     1   4
// 4:     2   3

public class DFS기본코드인접리스트 {

    ArrayList<Integer>[] arrayList;
    boolean[] visited;
    ArrayList<Integer> dfsList = new ArrayList<>();

    public DFS기본코드인접리스트(){
        Scanner sc = new Scanner(System.in);

        int vertex = sc.nextInt();
        int line = sc.nextInt();
        int startVertex = sc.nextInt();

        arrayList = new ArrayList[vertex + 1];

        for(int i = 0; i < arrayList.length; i++){
            arrayList[i] = new ArrayList<>();
        }

        visited = new boolean[vertex + 1];

        for(int i = 0; i < line; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();

            arrayList[x].add(y);
            arrayList[y].add(x);
        }

        for(int i = 1; i < vertex + 1; i++){
            Collections.sort(arrayList[i]);
        }

        dfs(startVertex);

        for(int integer : dfsList){
            System.out.println(integer + " ");
        }
        System.out.println();
    }

    public void dfs(int x){
        if(visited[x]) return;

        visited[x] = true;
        dfsList.add(x);

        for(int y : arrayList[x]){
            if(!visited[y]) dfs(y);
        }
    }

    public static void main(String[] args) {
        new DFS기본코드인접리스트();
    }
}

 

 

인접 리스트 형태

• 1번 정점: [2, 3]
• 2번 정점: [1, 4]
• 3번 정점: [1, 4]
• 4번 정점: [2, 3]

DFS 탐색 과정

초기 입력:

• 정점(vertex) = 4
• 간선(line) = 4
• 시작 정점(startVertex) = 1

1. 초기화 및 데이터 입력
   • arrayList[]는 각 정점에 대해 빈 리스트로 초기화됩니다.
   • 정점 간의 연결 정보를 바탕으로 각 정점의 인접 리스트가 구성됩니다.
   • 인접 리스트는 각 정점에 대해 오름차순으로 정렬됩니다 (필요에 따라).
2. dfs(1) 호출:
   • visited[1]를 true로 설정하고, 1을 출력(혹은 dfsList에 추가).
   • 1번 정점과 연결된 정점들을 탐색:
     • 2번 정점이 방문되지 않았으므로 dfs(2) 호출.
3. dfs(2) 호출:
   • visited[2]를 true로 설정하고, 2를 출력.
   • 2번 정점과 연결된 정점들을 탐색:
     • 1번 정점은 이미 방문했으므로 무시.
     • 4번 정점이 방문되지 않았으므로 dfs(4) 호출.
4. dfs(4) 호출:
   • visited[4]를 true로 설정하고, 4를 출력.
   • 4번 정점과 연결된 정점들을 탐색:
     • 2번 정점은 이미 방문했으므로 무시.
     • 3번 정점이 방문되지 않았으므로 dfs(3) 호출.
5. dfs(3) 호출:
   • visited[3]를 true로 설정하고, 3을 출력.
   • 3번 정점과 연결된 정점들을 탐색:
     • 1번 정점은 이미 방문했으므로 무시.
     • 4번 정점은 이미 방문했으므로 무시.

모든 연결된 정점이 탐색되었으므로 DFS 탐색이 종료됩니다.