DFS설명, 문제에서 발생하기 쉬운 실수들, 사용팁[C++]

1. DFS란

간단하게 설명하면, 임의의 노드에서 시작하여 그 그래프를 탐색하는 방법으로, 깊이우선탐색이라는 이름에 맞게, 한쪽 방향으로 계속 가다가 더이상 갈수 없게 되면 돌아오는 방식이다.

 

2. DFS 구현 

일반적으로 DFS의 경우, 재귀함수를 사용한다.(stack을 사용하기도 하지만, 재귀함수가 조금더 유명하다.)

또한, 문제유형에따라, 인접리스트와 인접행렬을 사용한다.

인접행렬을 사용했을때 메모리가 충분할 경우(일반적으로 노드개수 n<1000) 인접행렬을 사용하고

노드의 개수는 많지만 간선개수는 그에 비해 적을경우(n>1000, 간선 수< n^2)인접리스트를 사용한다

 

인접리스트의 경우

vector < vector<int>> graph; 를 통해 그래프를 만들고

인접 행렬의 경우 

int[1000][1000] graph;를 통해 그래프를 만든다. 

 

DFS문제 유형중 상하좌우 이동식 문제들이 있는데 ex) 백준 2178번 미로찾기

이 문제들은 인접 행렬방식을 사용하여 구현하면 된다. 

 

일반적으로 인접행렬 방식은 상대적으로 쉽기 때문에, 인접리스트 방식의 코드를 보면서 이야기해 보겠다. 

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector < vector<int>> graph;
int visit_dfs[1010];
vector<int> vec1;
int n, m, v, num;
int a1, a2;
void DFS(int a) { //재귀함수 방식 
	visit_dfs[a] = 1; //방문체크 
	printf("%d ",a);
		for (int i = 0; i < graph[a].size(); i++) { 
			if (visit_dfs[graph[a][i]] != 1) //방문하지 않은 노드만 방문 
				DFS(graph[a][i]);
		}
}

int main() {
	scanf("%d %d %d",&n,&m,&v);
	for (int i = 0; i <= n; i++) {
		graph.push_back(vec1); //2차원 벡터를 사용하기 위한 방식 
	}
	for (int i = 1; i <= m; i++) { //그래프 입력받기 
		scanf("%d %d",&a1,&a2);
		graph[a1].push_back(a2); 
		graph[a2].push_back(a1); //무향 그래프이므로 양방향 모두 넣어줘야함. 
	}
	DFS(v);
}

 

3. DFS에서 자주 발생하는 실수들

 

1. vector사이즈에 맞춰서 index를 참조했는지 확인해야한다. 특히 런타임 에러는 이거일 가능성이 높다.

2. 무향 그래프인데 한방향만 넣어준것이 아닌지, 반대로 유향 그래프인데 양쪽 다넣은 것이 아닌지 확인해야한다.

3. 방문한 노드를 재방문 하는게 아닌지 확인해야한다. 주로 시간초과가 발생하면 이거일 가능성이 높다. 

4. 상하좌우 탐색 문제나 인접행렬로 풀었을 경우, 배열의 경계를 잘 확인해줘야한다. 이게 잘못되면, 런타임 에러혹은 잘못된 결과가 나올 가능성이 높다. 

ex)상하좌우 탐색문제의 확인 예시  if (point2.x < 1 || point2.x > n || point2.y < 1 || point2.y > m)

5. DFS문제중에 함수가 종료되기전 전역배열, 전역변수의 값을 원상태로 복구해야하는 경우가 있는데, 이걸 까먹는 경우가 흔하다. 이것도 자주 발생하는 오류중 하나이다. 주로 백트래킹시 방문여부, 거리등의 값을 그런식으로 처리한다. 

 

4. DFS를 사용하는 문제인지 파악하는 방법

1. 일반적으로 전그래프를 전부 탐색해야하는데, 최단거리가 아니면 DFS일 가능성이 높다.(최단거리 쪽이면 BFS일것이다)

2. 미로찾기등의 문제에서 자주사용된다. (가장빠르게면 BFS를 쓰겠지만)

3. 연결되어있는지 여부를 확인할때도 자주사용된다.