DFS(Depth First Search)

허준기·2025년 1월 21일

DFS 알고리즘

알고리즘

목록 보기

7/10

DFS 는 그래프 탐색 방법 중 하나다

BFS 블로깅

관련된 내용은 바로 전 블로그에서 찾아볼 수 있으니 참고해주세요

오늘은 DFS 차례..

DFS(Depth-First Search)

트리나 그래프를 탐색하는 기법 중 하나로, 시작 노드에서 자식 노드들을 순서대로 탐색하며 깊이를 우선으로 탐색하는 알고리즘

하나의 순환 알고리즘으로 백트래킹에 상요하는 대표적인 탐색 알고리즘

루트노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식 → 주로 재귀함수 또는 Stack 으로 구현

탐색 과정

현재 노드 방문 표시

방문한 표시가 되어 있지 않은 각각의 인접한 정점 탐색

더 이상 방문하지 않은 정점이 없으면 이전 정점으로 돌아감(BackTracking)

모든 정점을 방문할 때까지 반복

DFS 애니메이션 참고 블로그

동작 방법은 위의 블로그에 있는 gif를 보면 될 것 같다
쉽게 말해서 한 방향으로 끝까지 탐색하고, 더 이상 탐색할게 없으면 이전 노드로 돌아가서 방문하지 않은 노드를 탐색하는 그런 방식이다

이론은 이해가 되지만 코드적으로 어떻게 구현해야 될까?
그건 문제를 풀면서 고민해보자

백준 11123번 양 한마리... 양 두마리...

양 한마리...

양 두마리... 양 세마리... 양 네마리... 양 다섯마리...

장난은 여기까지 하고 문제를 한번 살펴보자!

문제

# 과 . 으로 표현된 그리드 → # 은 양을 표현하고 . 은 풀을 표현한다
이 때, 양이 붙어 있으면 한 무리로 판단하고, 떨어져 있으면 다른 무리로 판단한다.
주어진 그리드에서 양 무리가 몇 개인지 구해라!

입력

T : 테스트 케이스의 수
H : 그리드의 높이
W : 그리드의 너비
W개의 문자로 이루어진 문자열을 H만큼 입력 받음 → 양과 풀 입력

2
4 4
#.#.
.#.#
#.##
.#.#
3 5
###.#
..#..
#.###

출력

각 케이스의 양의 무리 개수 출력

6
3

풀이

BFS 랑 비슷한 느낌이었다

양(#)을 만나면 상하좌우 검사를 한다 - 순서는 임의로 정함
그 과정에서 다시 양을 만나면 상하좌우 검사

이런식으로 재귀를 이용해서 해결해나가는 방법이다

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

public class P11123 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());

        for (int k = 0; k < t; k++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int h = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            String[][] grid = new String[h][w];

            for (int i = 0; i < h; i++) {
                String line = br.readLine();
                for (int j = 0; j < w; j++) {
                    grid[i][j] = String.valueOf(line.charAt(j));
                }
            }

            int count = 0;
            for(int i = 0; i < h; i++){
                for(int j = 0; j < w; j++){
                    if(grid[i][j].equals("#")){
                        dfs(grid, i, j, h, w);
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }

    private static void dfs(String[][] grid, int x, int y, int h, int w) {
        if(x < 0 || x >= h || y < 0 || y >= w || !grid[x][y].equals("#")){
            return;
        }

        grid[x][y] = ".";

        dfs(grid, x - 1, y, h, w);
        dfs(grid, x + 1, y, h, w);
        dfs(grid, x, y - 1, h, w);
        dfs(grid, x, y + 1, h, w);
    }
}