[알고리즘] 깊이 우선 탐색(DFS: Depth First Search, 백준 11724, 2606, 11724, 2667 -Java)

[알고리즘] 깊이 우선 탐색 -Java(DFS: Depth First Search, 백준 11724, 2606, 11724, 2667 -Java)

알고리즘 공부를 계속 미루는 제 자신을 보고 이대로는 안되겠다 싶어 😇
본격적으로 코딩테스트를 준비(+알고리즘 공부) 해보려고 합니다.
물론 혼자하면 작심삼일이 될거 같아
무료 Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의
강의 커리큘럼에 맞춰 공부해보자!!

[무료] Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의

깊이 우선 탐색(DFS)

깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나 입니다.
시간 복잡도는 O(V+E) 입니다.(V: 노드 수, E: 엣지 수)

 

완전 탐색 이란?
가능한 모든 경우의 수를 다 확인해서 정답을 찾는 방법입니다.
예를 들어 🔒자물쇠 비밀번호가 3자리로 구성되어 있다고 하면
반드시 풀 수 있는 방법은 000부터 999까지 모두 시도해보는 것 입니다.!🔓

 

깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 입니다.

 

재귀함수로 구현하거나 스택 자료구조를 이용합니다.
기본적으로 컴퓨터 자체가 스택의 원리를 사용하여 메소드를 실행하기 때문 입니다.

 

참고
JVM은 메소드를 호출할 때마다 Runtime Data Area에 Stack Area를 사용 합니다.^^
정확히는 메소드는 Stack Area에 Operand Stack 공간 push되고 pop됩니다.
따라서 재귀 함수와 스택은 동일하게 동작합니다.
알고리즘 재귀(Recursion -java)
10분 테코톡 나는 JVM를 모르고 개발했다.

 

깊이 우선 탐색은 재귀 함수를 이용하기 때문에 stackOverflow에 유의해야 합니다.(종료 조건이 반드시 있어야 합니다.)
깊이 우선 탐색을 응용하여 해결할 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있습니다.

 

DFS 핵심 이론

DFS는 한 번 방문한 노드를 다시 방문하면 안되기 때문에 노드 방문 여부를 확인할 배열이 필요 합니다.
스택에 노드를 삽입(push)할 때 방문 배열을 확인하고, 스택에서 노드를 뺄(pop) 때 탐색 순서에 기록하며, 인접 노드를 방문 배열과 대조하여 탐색합니다.

 

장점

• 찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있습니다.
• 경로상의 노드를 기억하기 때문에 적은 메모리를 사용합니다.

 

단점

• 재귀 함수를 이용하기 때문에, 함수 호출 비용이 추가적으로 들어가게 됩니다.
• 재귀 깊이가 지나치게 깊어지면 메모리 비용을 예측하기 어렵습니다.
• 최단 경로를 알 수 없습니다.

 

정리

• 그래프를 인접 리스트로 표현
• 방문 배열 설정
• 탐색 순서 설정
• 스택 설정
  • 시작점 스택에 push
  • 시작점 방문 배열에 체크
  • 탐색 순서에 시작점 삽입
    • 스택에 있는 값이 인접 노드가 있으면 인접 노드 push
      • 방문 배열에 체크
    • 스택에 있는 값이 인접 노드가 없으면 pop
      • 탐색 순서에 pop한 값 넣기
  • 스택이 비어 있을 때 까지 반복

 

이를 그림으로 표현 해보겠습니다.

백준 11724

11724번: 연결 요소의 개수
연결 리스트로 어떻게 표현해야하는지 몰라서 스스로 해결하지 못했습니다.😭

 

풀이

// 연결 요소의 갯수
public class Quiz11724 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        // 노드 갯수
        int n = Integer.parseInt(st.nextToken());
        // 엣지 갯수
        int m = Integer.parseInt(st.nextToken());

        // 인접 리스트 생성(index가 해당 노드 값, 값이 해당 노드의 인접 노드 값)
        // 노드 값이 1부터 시작하기 때문에(u가 1이상) index = 0 은 사용하지 않음
        // 초기화
        List<Integer>[] linkedList = new ArrayList[n+1];
        for(int i = 1; i <= n; i++) {
            linkedList[i] = new ArrayList<>();
        }
        // 인접 리스트 저장
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            // 양 끝점
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            // 방향이 없기 때문에 양쪽으로 저장
            linkedList[u].add(v);
            linkedList[v].add(u);
        }
        // [null, [2, 5], [1, 5], [4], [3, 6], [2, 1] [4]]

        // 방문 확인 배열 생성(u가 1부터 시작하기 때문에 index = 0은 사용 X)
        boolean[] visited = new boolean[n+1];
        int result = 0; // 요소 갯수(완전 탐색이 완료되면 1씩 증가 한다)
        // u = 1 부터 dfs 시작
        for(int i = 1; i <= n; i++) {
            // 방문하지 않은 경우에만 dfs 실행
            if(!visited[i]) {
                dfs(linkedList, visited, i);
                result++;
            }
        }
        System.out.println(result);
    }

    private static void dfs(List<Integer>[] linkedList, boolean[] visited, int i) {
        // 방문한 이력이 있으면 실행 종료
        if(visited[i]) return;
        // 방문한 이력이 없으면 dfs 실행
        else {
            // 방문했다고 변경
            visited[i] = true;
            // 인접 노드의 크기만큼 탐색
            for(int k = 0; k < linkedList[i].size(); k++) {
                // 탐색을 원하는 노드의 인접 노드
                Integer v = linkedList[i].get(k);
                // 인접 노드가 방문 이력이 없으면 dfs 실행
                if(!visited[v]) {
                    dfs(linkedList, visited, v);
                }
            }
        }
    }
}

백준 2606

2606번: 바이러스
DFS를 구현할 줄 알면 쉽게 해결할 수 있는 문제 입니다.

 

못 풀었더라도 너무 실망하지마세요!
하나 하나씩 연습하다보면 어느새 당신의 스택에 알고리즘 해결 능력이 많이 쌓여있을 것 입니다!!!
화이팅 합시다.^^

 

풀이

public class Quiz2606 {
    // 1번 노드와 연관 있는 컴퓨터 갯수 출력
    static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 노드 수(컴퓨터 갯수)
        int nodeNum = Integer.parseInt(br.readLine());
        // 간선 갯수(네트워크 연결 수)
        int edgeNum = Integer.parseInt(br.readLine());

        // 인접 리스트 생성
        // 컴퓨터는 1번부터 시작(0번 index를 사용하지 않는다.)
        List<Integer>[] linkedList = new ArrayList[nodeNum+1];
        // 초기화
        for(int i = 1; i <= nodeNum; i++ ){
            linkedList[i] = new ArrayList<>();
        }

        for(int i = 1; i <= edgeNum; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            // 양방향 관계
            linkedList[start].add(end);
            linkedList[end].add(start);
        }

        // 방문 이력 배열 생성(컴퓨터는 1번 부터 시작, index가 컴퓨터 번호임)
        boolean[] visited = new boolean[nodeNum+1];
        // 1번 컴퓨터만 dfs 실행
        dfs(linkedList, visited, 1);
        System.out.println(count);
    }

    private static void dfs(List<Integer>[] linkedList, boolean[] visited, int i) {
        if(!visited[i]) {
            visited[i] = true;
            for (int k = 0; k < linkedList[i].size(); k++) {
                Integer v = linkedList[i].get(k);
                if (!visited[v]) {
                    dfs(linkedList, visited, v);
                    count++;
                }
            }
        }
    }
}

백준 1012

1012번: 유기농 배추
배추밭에서 상, 하, 좌, 우로 움직여서 새로운 위치를 탐색해야 한다는 것을 생각하지 못하여 스스로 해결하지 못했습니다.😭

 

풀이

public class Quiz1012 {

    static int width = 0;
    static int height = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 테스트 갯수
        int t = Integer.parseInt(br.readLine());
        for(int i = 0; i < t; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            // 배추 밭의 가로 길이(-)
            width = Integer.parseInt(st.nextToken());
            // 배추 밭의 세로 길이(|)
            height = Integer.parseInt(st.nextToken());
            // 배추 위치 갯수
            int positionNum = Integer.parseInt(st.nextToken());

            // 배추 밭 배열
            int[][] field = new int[width][height];
            for(int k = 0; k < positionNum; k++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                field[x][y] = 1;
            }

            // 배추 밭 탐색 방문 이력
            boolean[][] visited = new boolean[width][height];
            // 지렁이 갯수(탐색을 마치면 지렁이 1 증가)
            int count = 0;
            for(int x = 0; x < width; x++) {
                for(int y = 0; y < height; y++) {
                    // 배추밭에 배추가 있고, 방문 이력이 없으면 탐색(bfs)
                    if(field[x][y] == 1 && !visited[x][y]) {
                        dfs(field, visited, x, y);
                        count++;
                    }
                }
            }
            sb.append(count).append("\n");
        }
        System.out.println(sb);
    }

    private static void dfs(int[][] field, boolean[][] visited, int x, int y) {
        visited[x][y] = true;
        // 배추가 있는 곳을 중심으로 상, 하, 좌, 우 탐색 해야함
        // 상, 하, 좌, 우 1칸씩만 이동이 가능함
        int[] upAndDown = {1, -1, 0, 0};
        int[] leftAndRight = {0, 0, 1, -1};
        for(int i = 0; i < 4; i++) {
            // 탐색 위치
            int newX = x + upAndDown[i]; // 기존 위치 + 이동 위치 = 새로운 위치
            int newY = y + leftAndRight[i]; // 기존 위치 + 이동 위치 = 새로운 위치

            // 배추 밭 범위를 벗어난 경우
            // 배추 밭은 0부터 시작하기 때문에 새로운 위치가 width 또는 height랑 같으면 안됨
            if(newX < 0 || newX >= width || newY < 0 || newY >= height) {
                continue;
            }

            // 새로운 위치에 배추가 있고, 탐색 이력이 없다면 탐색 한다.
            if(field[newX][newY] == 1 && !visited[newX][newY]) {
                dfs(field, visited, newX, newY);
            }
        }
    }
}

백준 2667

2667번: 단지번호붙이기
주어진 지도 배열을 한줄 씩 읽어서 지도에 넣어야 해서 좀 해맸습니다.
위 문제와 마찬가지의 방식으로 해결하면 됩니다.

 

풀이

package backjoon.search.dfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Quiz2667 {
    static int n = 0;
    static int houseCount = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 지도의 크기(정사각형임)
        n = Integer.parseInt(br.readLine());

        // 지도 배열
        int[][] map = new int[n][n];
        for(int i = 0; i < n; i++) {
            // 한줄로 읽어와서
            String str = br.readLine();
            // char로 변환
            char[] chars = str.toCharArray();
            for(int j = 0; j < n; j++) {
                // 아스키코드로 값을 읽어옴
                int data = chars[j] - '0';
                map[i][j] = data;
            }
        }


        // 탐색 이력 배열
        boolean[][] visited = new boolean[n][n];
        // 총단지 수
        int townNum = 0;
        // 집 수
        int houseNum = 1;
        // 각 단지의 집 수를 저장하는 배열
        List<Integer> houseNumList = new ArrayList<>();
        for(int x = 0; x < n; x++) {
            for(int y = 0; y < n; y++) {
                // 탐색 이력이 없고, 지도에 집이 있으면 탐색을 한다.
                if(!visited[x][y] && map[x][y] == 1) {
                    dfs(map, visited, x, y);
                    townNum++;
                    houseNumList.add(houseCount);
                    houseCount = 0;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(townNum).append("\n");
        // 오름차순 정렬
        houseNumList.sort(Comparator.naturalOrder());
        for(Integer i : houseNumList) {
            sb.append(i).append("\n");
        }

        System.out.println(sb);

        br.close();
    }

    private static void dfs(int[][] map, boolean[][] visited, int x, int y) {
        houseCount++; // 아파트 수 증가
        visited[x][y] = true;
        int[] upAndDown = {1, -1, 0, 0};
        int[] leftAndRight = {0, 0, 1, -1};
        for(int i = 0; i < 4; i++) {
            int newX = x + upAndDown[i]; // 탐색할 새로운 위치
            int newY = y + leftAndRight[i]; // 탐색할 새로운 위치

            // 탐색 위치를 벗어나는 경우
            if(newX < 0 || newY < 0 || newX >= n || newY >= n) {
                continue;
            }

            // 새로운 탐색 위치에 방문한 적이 없고, 집이 있으면 탐색을 한다.
            if(!visited[newX][newY] && map[newX][newY] == 1) {
                dfs(map, visited, newX, newY);
            }
        }
    }
}