DFS

DFS(Depth First Search)

• 그래프 순회 방법 중 하나(깊이 우선 탐색)
• 시작 노드에서 깊이가 커지는 방향으로 탐색을 진행하여 더 이상 방문할 인접 노드가 없는 경우 이전 노드가 돌아가서, 다시 깊이 우선 탐색을 반복하게 됨.
• 재귀 호출을 통해 구현

1.

입력 5(노드의 개수) 6(간선의 개수)

노드의 쌍 0 1 0 2 1 3 1 4 2 4 3 4 (각 쌍들 사이에 간선이 존재)

출력 0 1 3 4 2

<코드>

#include <iostream>
#include <cstring>
using namespace std;
#define max 10
int n, e;
int graph[max][max];
bool visited[max];

void dfs(int node)
{
	visited[node] = true;
	cout<<node<<' ';
	//방문 노드 출력 
	for(int next=0;next<n; next++)
	{
		//간선이 있고, 방문여부 확인(방문하지 않았을 때, 탐색진행) 
		if(!visited[next] && graph[node][next]){
			dfs(next);
		}
	}
}
int main()
{
	cin>>n>>e;
	memset(visited, 0, sizeof(visited));
	memset(graph, 0, sizeof(graph));
	for(int i=0;i<e;i++)
	{
		int u,v;
		cin>>u>>v;
		graph[u][v]=graph[v][u]=1;
	}
	dfs(0);
	return 0;
}

2. 스택을 이용한 dfs 구현 (1번과 입력 동일)

출력 0 2 4 3 1(스택은 후입선출 구조이기 때문에, 출력이 기존 dfs와 다르게 나온다.)

<코드>

#include <iostream>
#include <cstring>
#include <stack>
//스택을 이용한 dfs구현
//재귀호출을 많이하면 스택오버플로우가 발생. 이를 많이하기 위해 전역변수로 선언  
#define max 10
int n, e;
int graph[max][max];
using namespace std;
void dfs(int node){
	bool visited[max] = {false}; // stack을 이용한 dfs구현은 재귀호출을 사용하지 않기 때문에 로컬변수로 초기화 
	stack<int> mystack;
	mystack.push(node);
	
	while(!mystack.empty()){
		int curr = mystack.top();
		mystack.pop();
		if(visited[curr]) continue;
		visited[curr]=true;
		cout<<curr<<'\n';
		for(int next=0;next<n;++next)
		{
			if(!visited[next] && graph[curr][next]){
				mystack.push(next);
			}
		}
	}



}

int main()
{
	cin>>n>>e;
	memset(visited, 0, sizeof(visited));
	memset(graph, 0, sizeof(graph));
	for(int i=0;i<e;i++)
	{
		int u,v;
		cin>>u>>v;
		graph[u][v]=graph[v][u]=1;
	}
	dfs(0);
	return 0;
}

2차원 dfs의 활용 (Flood fill algorithm)

• Flood fill algorithm이란, 시작점으로부터 상하좌우 연결된 부분을 찾아가는 알고리즘이다.
• 시작점으로부터 상하좌우 check를 해나가면서 확장시킬 수 있다.

<코드>

#include <iostream>
#include <cstring>
#include <stack>
#define max 10
int D[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; // 순서대로 왼쪽 오른쪽 위 아래를 의미 
using namespace std;
struct Point{
	int row,col; // 행,열 
};

int n, Board[max][max];
void dfs(int r,int c,int color)
{
	bool visited[max][max] = {false};
	stack<Point>mystack;
	mystack.push({r,c}); //기준점 push 
	while(!mystack.empty()){
		Point curr = mystack.top();
		mystack.pop();
		if(visited[curr.row][curr.col]) continue;
		visited[curr.row][curr.col] =true;
		Board[curr.row][curr.col] =color;
		for(int i=0;i<4;i++){
			int nr = curr.row+D[i][0], nc = curr.col+D[i][1]; //상하좌우 영역표시 
			if(nr<0 || nr>n-1 || nc<0 || nc>n-1) continue; //입력받은 n*n의 범위를 초과하는지 검사 
			if(visited[nr][nc]) continue; //방문했다면 skip 
			if(Board[nr][nc]) continue;//이미 영역표시를 했다면 skip 
			mystack.push({nr,nc}); 
		}
	}
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++){
			cin>>Board[i][j];
		}
	}
	int sr,sc,color;
	cin>>sr>>sc>>color; // 기준점 sr,sc 영역표시 color 
	dfs(sr,sc,color);
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cout<<Board[i][j]<<' ';
		}
		cout<<'\n';
	}
	
}

<출력>

 

기준점(1,1)을 바탕으로 주변영역이 3으로 값이 바꼈음을 확인할 수 있다.

<참고 자료>

https://www.youtube.com/watch?v=M48Po-wTOpU&list=PL6YHvWRMtz7DS3hVaqMazHujPcKVfblQa&index=5