DFS 관련 개념 정리

BFS, DFS 는 알고리즘 유형에서 많이 나오는 유형이다.

우선 탐색 관련 된 내용이다.

 

스택  =  pop,push로 선입 후추이다. 박스쌓기 처럼, 최상단 출력, peek()

큐 = 선입선출 , 줄서기, 대기열 같이, offer, poll 사용해서 사용

 

DFS : 깊이 우선 탐색, 스택 OR 재귀함수를 

탐색 시작 노드 스택에 삽입, 인접 노드 스택에 넣고

 

 

 

 

개념을 익히기에 좋은 문제라고 생각한다.

우선, 해당 부분을 이해 및 풀을려면 어떤식으로 돌아가야하는지 알아야한다.

1은 false , 0은 true로 이해하면 된다.

 

자, 그러면 코딩을 해보자

 

 

import java.util.*;

public class HelloCodiva {

    public static int n, m;
    public static int[][] graph = new int[1000][1000];

    // DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
    public static boolean dfs(int x, int y) {
        // 주어진 범위를 벗어나는 경우에는 즉시 종료
        if (x <= -1 || x >=n || y <= -1 || y >= m) {
            return false;
        }
        // 현재 노드를 아직 방문하지 않았다면
        if (graph[x][y] == 0) {
            // 해당 노드 방문 처리
            graph[x][y] = 1;
            // 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
            dfs(x - 1, y);
            dfs(x, y - 1);
            dfs(x + 1, y);
            dfs(x, y + 1);
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // N, M을 공백을 기준으로 구분하여 입력 받기
        n = sc.nextInt();
        m = sc.nextInt();
        sc.nextLine(); // 버퍼 지우기

        // 2차원 리스트의 맵 정보 입력 받기
        for (int i = 0; i < n; i++) {
            String str = sc.nextLine();
            for (int j = 0; j < m; j++) {
                graph[i][j] = str.charAt(j) - '0';
            }
        }

        // 모든 노드(위치)에 대하여 음료수 채우기
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 현재 위치에서 DFS 수행
                if (dfs(i, j)) {
                    result += 1;
                }
            }
        }
        System.out.println(result); // 정답 출력 
    }

}

 

해당 건 단순하다.

단순히 scanner로 받아서, 0인지 체크 맞으면 1로 변환, return true

count +1 만 해주면된다.

상하좌우에 대한 개념 2차원배열 개념만익히면 될듯하다.

 

 

쉽게 말하면, 재귀함수를 통해, 인접 한 -1,+1 을 해서, 해당을 식별할수있는 값으로 update를 치고,

해당 update 를 할수없으면, 본함수에서 for문으로 다음 인덱스를 탄다.

재귀함수를 호출했을때, 해당 재귀함수의 return 값은 중요하지않다. 마지막에 강제 return true를 주기 떄문에