🌓 DFS

💫 정의

---

BFS에서 큐 대신 스택을 쓰는

DFS Depth-First-Search
다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리듬

깊이를 우선으로 방문?
설명할 방법이 없다

원래 DFS는 그래프라는 자료구조에서 모든 노드를 방문하기 위한 알고리듬
그래프 : 정점과 간선으로 이루어진 자료구조

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
2. 스택에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입
4. 스택가 빌 때까지 2번을 반목 방문 표시를 남기기 때문에 모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N).
   행이 R개이고 열이 C개이면 O(RC)

BFS와 최종 결과는 똑같더라도, 방문 순서에 아주 큰 차이가 있다
BFS는 파문 퍼지듯 상하좌우로 퍼져나가는, 거리 순을 방문
DFS는 마인크래프트 땅굴 파듯 뭔가 한 방향으로 막힐 때까지 쭉 직진

BFS에서 현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 1만큼 떨어져있따는 성질이
DFS에서는 성립하지 않음
그래서 거리를 계산할 때는 DFS를 쓸 수 없음

그래서 다차원 배열에서 굳이 BFS 대신 DFS를 써야하는 일이 없다
Flood Fill은 어느것을 써도 되는데, 거리 측정은 BFS만 할 수 있으니 DFS를 쓸 일이 없다.
그래서 다차원 배열에서 순회하는 문제를 풀 때 BFS만 쓰게 된다

DFS는 나중에 그래프와 트리라는 자료구조를 배울 때 필요하게 된다

어느정도 정석적인 구현

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용

int board[502][502] = {
	{ 1, 1, 1, 0, 1, 0, 0, 0, 0, 0} ,
	{ 1, 0, 0, 0, 1, 0, 0, 0, 0, 0} ,
	{ 1, 1, 1, 0, 1, 0, 0, 0, 0, 0} ,
	{ 1, 1, 0, 0, 1, 0, 0, 0, 0, 0} ,
	{ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0} ,
	{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} ,
	{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} }; // 1이 파란 칸, 0이 빨간 칸에 대응
bool vis[502][502]; // visit 해당 칸을 방문했는지 여부를 저장
int n = 7, m = 10; // 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);

	stack<pair<int,int> > S;

	vis[0][0] = 1; // @ (0, 0)을 방문했다고 명시
	S.push({ 0, 0 }); // 큐에 시작점인 (0, 0)을 삽입.
	
	while(!S.empty())
	{
		pair<int,int> cur = S.top();
		S.pop();
		
		cout << '(' << cur.X << ", " << cur.Y << ") -> ";
		
		// 상하좌우 칸을 살펴볼 것이다.
		for (int dir = 0; dir < 4; dir++)
		{ 
			// nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];

			// @ 아랫조건보다 먼저, 범위 밖일 경우 넘어감
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
				continue; 
			// 이미 방문한 칸이거나 파란 칸이 아닐 경우
			if (vis[nx][ny] || board[nx][ny] != 1)
				continue;

			// (nx, ny)를 방문했다고 명시
			// @ 넣을때 표시하지 않고, 뺄 때 표시한다면 중복된 요소가 스택에 들어갈 수 있어서 메모리 초과, 시간 초과가 날 수 있다
			vis[nx][ny] = 1; 
			S.push({ nx, ny });
		}
	}
}

• Flood Fill
• 거리측정 (최단거리)
  • 방문 표시 대신 시작점과의 거리
  • -1로 초기화하면 방문 표시 여부도 알 수 있다
• 시작점이 여러 개
  • 여러 시작점을 큐에 다 넣으면 됨
  • BFS 성질 -> 큐에는 요소가 거리(시간) 순서대로 들어감 (큐에 요소가 쌓이는 순서는 거리 순)
• 시작점이 두 종류
  • 모두 BFS를 돌림
  • 하나를 먼저 BFS. 순서를 다르게 할 수 있다면 (전파가 서로 영향을 주지 않으면, 한쪽만 영향을 준다면)
  • 전파가 서로 영향을 준다면 -> 백 트래킹
• 1차원에서의 BFS
  • 단순히 전파가 좌우로만 이루어지는

🫧