DFS

PKH·2025년 1월 10일

DFS를 배울 때 DFS는 한 부분을 끝까지 탐지하기 전까지 돌아오지 않는다고 배웠다. 주어진 일을 마무리하기 전까지 작업을 하는데 뭔가 ~~나랑 상반돼서 배울 때 꽤나 충격이었다~~

1. DFS란

DFS란 Depth First Search의 약자로 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문한다. 쉽게 표현해보면 인접한 노드의 방문 순서를 정해둔다고 봐도 무방할듯하다.

(이미지 출처 : https://www.quora.com/What-is-the-algorithm-for-BFS-and-DFS)

알고리즘

노드가 들어오면 방문 카운트를 기록한 후 카운트를 1 증가시킨다.

인접한 노드가 존재한다면 재귀를 통해 1번 작업을 수행한다.

위 작업을 반복하여 전체 노드를 다 탐지했다면 종료한다.

2. 특징

장점

1) 메모리 효율성: 현 경로상의 노드만 기억하면 되므로 메모리 소모가 적다.
2) 깊은 목표 탐색: 목표 노드가 깊은 곳에 있다면 빠르게 탐색이 가능하다
단점

1) 비효율적 탐색 가능성: 목표 노드가 없는 경로에도 깊이 탐색을 수행할 수 있다.
2) 최단 경로 보장 없음: DFS는 항상 최단 경로를 찾는다는 보장이 없다.

3. 코드

#include <bits/stdc++.h>
using namespace std;

int board[502][502];
int vis[502][502];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1}; // 하 우 상 좌 순으로 탐지
int n,m;
int cnt=1;

void dfs(int i, int j)
{
	vis[i][j] = cnt++;
	
	for(int dir=0; dir<4; dir++)
	{
		int nx = dx[dir] + i, ny = dy[dir] + j;
		if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
		if(board[nx][ny] == 0 || vis[nx][ny] != 0) continue;
		dfs(nx,ny);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++) cin >> board[i][j];
		
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(board[i][j] == 0 || vis[i][j] != 0 ) continue;
			dfs(i,j);
		}
	}
	
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			cout.width(3);
			cout << vis[i][j];
		} cout << '\n';
	}
	
	return 0;
}