[이것이 코딩테스트다] chapter05. p134~p143 #DFS 개념정리

DFS(Depth-First Search)

깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

스택 자료구조 사용

그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문

 

인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식

DFS 수행순서

1) 탐색 시작 노드 스택에 삽입하고 방문처리
2) 방문 안한 인접노드 스택에 삽입하고 방문처리, 방문 안한 인접노드 없으면 최상단 노드 꺼냄
3) 반복

 

 

[이것이 코딩테스트다] DFS 자바 코드 

import java.util.*;

public class DFS {

    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // DFS 함수 정의
    public static void dfs(int x) {
        // 현재 노드를 방문 처리
        visited[x] = true;
        System.out.print(x + " ");
        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for (int i = 0; i < graph.get(x).size(); i++) {
            int y = graph.get(x).get(i);
            if (!visited[y]) dfs(y);
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 노드 1에 연결된 노드 정보 저장 
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);
        
        // 노드 2에 연결된 노드 정보 저장 
        graph.get(2).add(1);
        graph.get(2).add(7);
        
        // 노드 3에 연결된 노드 정보 저장 
        graph.get(3).add(1);
        graph.get(3).add(4);
        graph.get(3).add(5);
        
        // 노드 4에 연결된 노드 정보 저장 
        graph.get(4).add(3);
        graph.get(4).add(5);
        
        // 노드 5에 연결된 노드 정보 저장 
        graph.get(5).add(3);
        graph.get(5).add(4);
        
        // 노드 6에 연결된 노드 정보 저장 
        graph.get(6).add(7);
        
        // 노드 7에 연결된 노드 정보 저장 
        graph.get(7).add(2);
        graph.get(7).add(6);
        graph.get(7).add(8);
        
        // 노드 8에 연결된 노드 정보 저장 
        graph.get(8).add(1);
        graph.get(8).add(7);

        dfs(1);
    }

}

실행결과 : 1 2 7 6 8 3 4 5

 

DFS코드 공부