DFS . 4

DFS 구현 방법 :  1. Stack 으로 구현 ,  2. 재귀함수로 구현

 

 

 

 

 

 

 

 

 

DFS 동작 예시:  스택 자료구조인 경우

방문 기준: 번호가 낮은 인접 노드부터

 

 

 

DFS 코드 자바 예제 :  스택 자료구조를 사용한 경우

강의 영상 예시처럼 1 2 7 이렇게 스택에 쌓이는 코드

 

 

명 : 명령어

특 :  특수 명령어

자 : 변수 or 자료들

 

while (명)  +  isEmpty() 메서드 (특)

         if (명)  +  visited[ ] 배열 (자)                       - - >  방문처리  ( 방문했으면 넘어가고 ,  안 했으면 할 일 하고 )

   

        for (명)  +  graph 리스트 (자)  +  get 메서드 (특)       - - >  graph 리스트 순회

                if (명)  +  visited[ ] 배열 (자)                             - - >  방문처리   ( 방문했으면 넘아가고,  안 했으면 할 일 하고 )

     

                         break  (명)

 

 

public class DFSVisitAllPeek {
  public static void main(String[] args) {

                // 배열 선언
                // 객체 배열 요소 추가

                // 그래프 만들기 (간선 연결)

                //  인접 노드들 숫자순으로 정렬 (안전장치)
                ( boolean[] visited = new boolean[n + 1];    배열선언 n+1  )
                // for + dfs 함수를  이용하여 모든 노드 방문하기

   public static void dfsPeek(  ~~  ){
                  //  스택 선언
                 //  스택에 시작노드 push 하기

                 //  while + 스택이 빌 때까지 ( isEmpty() 메서드 )
                                 (방문처리)       

                             //  스택에서  peek 하기
                             //  peek 한거 방문 처리
                             //  boolean  이웃있다 변수 선언

 

                              ( graph 리스트 순회 )
                         //  for( int neighbor : graph.get(current) )  peek 노드의 인접 노드 순회
                                // if  방문 안 했으면 스택에 추가하고  이웃있다 변수 true로 바꾸고 break;
                       
                         //  이웃있다 변수가 false 면  스택에서 pop 하기

 

import java.util.*;

public class DFSVisitAllPeek {
    public static void main(String[] args) {
        int n = 8;

        // 그래프 초기화
        List<List<Integer>> graph = new ArrayList<>();  // 객체 배열 (방만 생겨서 직접 넣어줘야 함)
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());   // 객체 배열의 각 요소가 독립적인 객체가 되어야 하기 때문에 각각의 것을 직접 넣어줌
        }

        // 간선 연결
        graph.get(1).addAll(Arrays.asList(2, 3, 8));
        graph.get(2).addAll(Arrays.asList(1, 7));
        graph.get(3).addAll(Arrays.asList(1, 4, 5));
        graph.get(4).addAll(Arrays.asList(3, 5));
        graph.get(5).addAll(Arrays.asList(3, 4));
        graph.get(6).addAll(Arrays.asList(7));
        graph.get(7).addAll(Arrays.asList(2, 6, 8));
        graph.get(8).addAll(Arrays.asList(1, 7));

        // 인접 노드를 숫자순으로 정렬             // 일반적인 상황을 대비한 안전장치
        for (List<Integer> neighbors : graph) {
            Collections.sort(neighbors);
        }

        boolean[] visited = new boolean[n + 1];
        List<Integer> visitOrder = new ArrayList<>();

        // 전체 노드 다 방문하도록 루프
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                dfsPeek(graph, visited, i, visitOrder);
            }
        }

        // 방문 순서 출력
        System.out.println("방문 순서: " + visitOrder);
    }

    public static void dfsPeek(List<List<Integer>> graph, boolean[] visited, int start, List<Integer> visitOrder) {
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int current = stack.peek();  // peek으로 현재 노드를 확인

            if (!visited[current]) {
                visited[current] = true;
                visitOrder.add(current);
            }

            boolean hasUnvisitedNeighbor = false;

            for (int neighbor : graph.get(current)) {
                if (!visited[neighbor]) {
                    stack.push(neighbor);  // 방문 안 한 인접 노드 하나만 push
                    hasUnvisitedNeighbor = true;
                    break;
                }
            }

            if (!hasUnvisitedNeighbor) {
                stack.pop();  // 더 이상 갈 곳이 없으면 pop
            }
        }
    }
}

 

 

 

강의 영상과는 조금 다르게  (1) 8 3 (2) 8 7   이렇게 쌓이는 경우

import java.util.*;

public class DFSExample {
    public static void main(String[] args) {   // main 함수 : 그래프 세팅함
        // 노드 개수
        int n = 8;

        // 인접 리스트 생성 (1-based index)
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 그래프 간선 추가
        graph.get(1).addAll(Arrays.asList(2, 3, 8));
        graph.get(2).addAll(Arrays.asList(1, 7));
        graph.get(3).addAll(Arrays.asList(1, 4, 5));
        graph.get(4).addAll(Arrays.asList(3, 5));
        graph.get(5).addAll(Arrays.asList(3, 4));
        graph.get(6).addAll(Arrays.asList(7));
        graph.get(7).addAll(Arrays.asList(2, 6, 8));
        graph.get(8).addAll(Arrays.asList(1, 7));

        // 작은 숫자부터 방문하기 위해 정렬            // 일반적인 상황을 대비한 안전장치
        for (List<Integer> neighbors : graph) {    
            Collections.sort(neighbors);
        }

        boolean[] visited = new boolean[n + 1];
        dfsStack(graph, visited, 1); // 1번 노드부터 시작
    }

    public static void dfsStack(List<List<Integer>> graph, boolean[] visited, int start) {
        Stack<Integer> stack = new Stack<>();     // stack 자료구조
        stack.push(start);

        while (!stack.isEmpty()) {
            int node = stack.pop();

            if (!visited[node]) {
                visited[node] = true;
                System.out.print(node + " ");

                // 인접 노드를 역순으로 스택에 넣어야 작은 숫자부터 먼저 꺼내짐
                List<Integer> neighbors = graph.get(node);
                for (int i = neighbors.size() - 1; i >= 0; i--) {
                    int next = neighbors.get(i);
                    if (!visited[next]) {
                        stack.push(next);
                    }
                }
            }
        }
    }
}

---

 

---

 

 

---

 

 

DFS 코드 예제 :  재귀함수를 사용한 경우

(재귀함수로 구현하고 노드 방문 순서를 출력한 예시)

 

 

일반적으로 그래프 문제에서는 노드의 번호가 1번부터 시작하기 때문에
그래프를 초기화할 때 인덱스 0에 대한 내용은 비워두고 1번 인덱스부터 채운다

 

그렇기에 방문여부를 확인하는 리스트의 요소 개수를 노드 개수보다 1 높은 수로 선언하기

 

 

2차원 리스트를 선언할 때 숫자들을 작은 수부터 차례대로 써서
재귀함수를 통해 우리가 원하는 대로 출력이 되게 만들 수 있었다.

 

 

 

 

 

 

 

자바
ArrayList 는 특정 인덱스에 접근하기 위해 상수시간이 소요되기 때문에 일반 배열보다 더 좋다

ArrayList를 중첩된 형태로 이용해서 그래프를 표현할 수 있다

 

 

import java.util.*;

public class Main {

    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);
    }

}