DFS 정리 (c++)

바킹독알고리즘 블로그 보고 정리한 내용입니다

출처: https://blog.encrypted.gg/942

[실전 알고리즘] 0x0A강 - DFS

 

DFS (Depth First Search)

다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘

 

BFS와 마찬가지로 모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 N개 일 때 O(N)

 

	0	1	2	3
0	0,0	0,1	0,2	0,3
1	1,0	1,1	1,2	1,3
2	2,0	2,1	2,2	2,3
3	3,0	3,1	3,2	3,3

(0,0)에서 시작할 경우 상,하,좌,우 탐색

 

1. (0,0) 시작

(0,0) push

스택 : (0,0)

 

2. (0,0) 주변 (0,1), (1,0) 탐색

(0,0) pop

(0,1), (1,0) push

스택 : (0,1), (1,0)

 

3. (1,0) 주변 (2,0) 탐색

(1,0) pop

(2,0) push

스택 : (0,1), (2,0)

 

4. (2,0) 주변 (2,1), (3,0) 탐색

(2,0) pop

(2,1), (3,0) push

스택 : (0,1), (2,1), (3,0)

 

5. (3,0) 주변 없음

(3,0) pop

스택 : (0,1), (2,1)

 

6.(2,1) 주변 (2,2) 탐색

(2,1) pop 

(2,2) push

스택 : (0,1), (2,2)

 

7. (2,2) 주변 (1,2) 탐색

(2,2) pop

(1,2) push

스택 : (0,1), (1,2)

 

8. (1,2) 주변 (0,2) 탐색

(1,2) pop

(0,2) push

스택 : (0,1), (0,2)

 

9. (0,2) 주변 없음

(0,2) pop

스택 : (0,1)

 

10. (0,1) 주변 없음

(0,1) pop

스택 : empty

 

스택에 아무것도 남지 않으면, 탐색 완료한다.

 

DFS 순서

1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김
2. 스택에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입
4. 스택이 빌 때까지 2번을 반복

 

DFS 코드

1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김

stack<pair<int, int>> S;
S.push({0,0});
vis[0][0] = 1;

2. 스택에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행

stack<int, int>> cur = S.top();
S.pop();

for(int i = 0; i < 4; i++) {
	int nx = cur.first + dx[i];
    int ny = cur.second + dy[i];
}

3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입

if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(vis[nx][ny] || board[nx][ny] != 1) continue;
vis[nx][ny] = 1;
S.push({nx,ny});

4. 스택이 빌 때까지 2번을 반복

while(!S.empty()) {
 // 위에 작성한 코드 이 안에 넣기
}

 

5. 최종코드

#include <bits/stdc++.h>
using namespace std;
int board[502][502];
bool vis[502][502];
int n, m; // n = 행의 수, m = 열의 수
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(void){
  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];
    }
  }
  
  stack<pair<int,int> > S;
  vis[0][0] = 1;
  S.push({0,0});
  
  while(!S.empty()){
    pair<int,int> cur = S.top(); 
    S.pop();
    
    for(int i = 0; i < 4; i++){
      int nx = cur.first + dx[dir];
      int ny = cur.second + dy[dir];
      
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; 
      if(vis[nx][ny] || board[nx][ny] != 1) continue;
      
      vis[nx][ny] = 1;
      S.push({nx,ny});
    }
  }
}

BFS랑 달라진건

stack 이란것

stack의 top을 현재 노드로 삼고 탐색하는것

 

BFS에서 시작점으로 부터의 거리를 담을 때, DFS는 순회방식이 달라서 한칸씩 멀어질때 +1 을 해주는 계산을 해주는 문제랑 맞지 않다.

BFS는 시작점에 돌 던지면 사방으로 퍼지는 그림이라면

DFS는 한 지점에서 끝을 본다음에 다른 방향으로 흘러가니깐요

 

그래서 다차원 배열에서 탐색이 필요한 문제는 굳이 BFS대신 DFS를 쓸 일이 없다.

단 나중에 그래프나 트리에서는 DFS가 필요해서 DFS의 개념 자체는 알고 있을 필요가 있다고 함.