728x90
DFS(Depth First Search) / 깊이 우선 탐색
DFS 는 후에 설명될 BFS 와 함께 대표적이고 가장 기초적인 길찾기 알고리즘입니다.
깊이 우선 탐색이라는 이름에 걸맞게 우선 깊게 파고들어가고 보는 알고리즘이라고 볼 수 있는데, 일반적으로 복잡하지 않은 길 찾기 문제나 어떤 그래프가 몇 개의 그룹으로 존재하는지 찾는데 많이 사용하곤 합니다. 또 스택(Stack) 이라는 자료구조를 사용하는 것이 특징이며 후입선출이라는 스택의 특징을 잘 이용한 알고리즘입니다. 혹은 재귀 함수로 스택을 사용하지 않고 구현할 수 있지만 후입선출이라는 특징은 여전히 사용됩니다.
DFS 를 사용하는 상황에서의 단계를 크게 나누자면 아래와 같습니다.
1. 데이터를 입력
2. 데이터에서 그래프 혹은 트리를 생성 ( 특정 노드에서 이동 가능한 노드를 정리 )
3. 시작점을 스택에 삽입
4. 스택의 탑 ( 가장 마지막에 들어온 데이터 ) 에서 이동 가능한 노드를 탐색
5-1. 조건에 부합하는 노드를 스택에 삽입 ( 인덱스, 방문 여부, 문제 조건 등 )
5-2. 조건에 부합하는 노드가 없다면 스택의 탑을 제거 ( 팝 )
6-1. 목표 노드가 없다면 ( 그룹을 탐색하는 문제 등 ) 4~5 를 스택이 빌 때 까지 반복
6-2. 목표 노드가 존재한다면 목표노드에 도달할 때 까지 반복
주의할점은 일반적인 문제에서는 탐색 가능한 노드를 탐색할 때 이미 거쳐온 노드로 돌아갈 수 있으므로 방문 목록을 만들어 방문하지 않은 노드만 스택에 입력하도록 해야합니다. 이 과정에서 단순하게 array 혹은 list 를 사용할 수도 있지만 객체지향언어에서는 class 혹은 struct 를 만들어 노드에 따로 체크를 해둘수도 있습니다.
코딩 테스트 준비를 한다면 가장 쉽게 마주칠수 있는 두 유형으로 정수 좌표 평면위에 존재하는 격자를 탐색하는 문제와 임의의 좌표평면 위에 존재하는 포인트들을 탐색하는 문제가 있습니다.
격자를 탐색하는 경우 움직이는 방향을 가이드해주는 리스트를 만들어 순차적으로 탐색하게 도와주면 되고,
포인트를 탐색할 경우 이동 가능 포인트를 순회해주면 됩니다.
코드
코드는 4 종류로
python 과 C++
stack 과 recursion
으로 분류되어 있고 array, list 가 아닌 struct, class 를 사용하는 방식도 작성하려 했지만 간단한 문제에서는 굳이 사용할 필요가 없으므로 생략했습니다.
또한 각 코드는 파이썬스럽게, C++ 스럽게 보다는 최대한 비슷하게 작성해 다른 언어간에 이해를 돕고자 했습니다.
[ C++, array, stack]
더보기
#include <iostream>
#include <vector>
#include <array>
using namespace std;
// visited array + stack
vector<array<int, 2>> DFS_array_stack(array<array<int, 10>, 10>& map_arr, int& N, int& M) {
// 이동 가이드, 4 방향
array<array<int, 2>, 4> move_guide;
move_guide[0] = { 0, 1 };
move_guide[1] = { 1, 0 };
move_guide[2] = { 0, -1 };
move_guide[3] = { -1, 0 };
// 모든 이동경로 기록
vector<array<int, 2>> routes;
// 스택
vector<array<int, 2>> stk = { {0, 0} };
// 방문 목록
array<array<bool, 10>, 10> visited;
// 방문 목록 true 로 초기화
for (int i = 0; i < 10;i++) visited[i].fill(true);
// 스택이 빌 때 까지 탐색
while (!stk.empty()) {
// 현재 인덱스
int now_x = stk.back()[0];
int now_y = stk.back()[1];
// 방문 기록
visited[now_x][now_y] = false;
// 이동경로 기록
routes.push_back({ now_x, now_y });
// 이동 가이드를 따라 네방향 탐색
for (int i = 0; i < 4;i++) {
// 다음 후보 인덱스
int next_x = now_x + move_guide[i][0];
int next_y = now_y + move_guide[i][1];
//// 후보 인덱스가 조건에 부합하면
// 인덱스 범위안에 존재하는지
// 방문한적 없는 인덱스인지
// 벽이 아닌지
if ((next_x >= 0 and next_x < N) and
(next_y >= 0 and next_y < M) and
(visited[next_x][next_y]) and
(map_arr[next_x][next_y] == 0)) {
// 스택에 삽입
stk.push_back({ next_x, next_y });
// 바로 다음 인덱스 탐색
break;
}
// 조건에 부합하는 후보 인덱스가 존재하지 않으면
else if (i == 3) {
// 스택에서 팝
stk.pop_back();
}
}
}
return routes;
}
int main(void) {
// 격자의 크기, 행 / 열
int N = 10;
int M = 10;
// 맵 생성, 0 : 길 / 1 : 벽
array<array<int, 10>,10> map_arr;
map_arr[9] = { 1, 0, 1, 1, 0, 0, 0, 1, 0, 0 };
map_arr[8] = { 0, 0, 1, 1, 0, 1, 0, 0, 0, 1 };
map_arr[7] = { 1, 0, 0, 1, 0, 1, 1, 0, 1, 1 };
map_arr[6] = { 0, 0, 0, 1, 1, 0, 0, 0, 1, 0 };
map_arr[5] = { 1, 1, 0, 1, 0, 1, 1, 0, 1, 0 };
map_arr[4] = { 0, 0, 0, 1, 0, 1, 0, 0, 0, 0 };
map_arr[3] = { 1, 1, 0, 0, 0, 0, 0, 1, 1, 0 };
map_arr[2] = { 1, 1, 0, 1, 0, 1, 0, 0, 1, 1 };
map_arr[1] = { 1, 0, 0, 1, 0, 0, 1, 0, 1, 0 };
map_arr[0] = { 0, 0, 1, 0, 0, 1, 1, 1, 1, 0 };
cout << "[ ";
for (auto arr : DFS_array_stack(map_arr, N, M)) {
cout << "[ " << arr[0] << " " << arr[1] << " ] ";
}
cout << "]\n";
}[ C++, array, 재귀]
더보기
#include <iostream>
#include <vector>
#include <array>
using namespace std;
// 이동 경로
vector<array<int, 2>> route;
// visited array + reculsion
void DFS_array_reculsion(array<array<int, 10>, 10>& map_arr, array<array<bool, 10>, 10>& visited, int& N, int& M, int now_x, int now_y) {
// 이미 방문한 노드면 종료
if (!visited[now_x][now_y]) return;
// 이동 가이드, 4 방향
array<array<int, 2>, 4> move_guide;
move_guide[0] = { 0, 1 };
move_guide[1] = { 1, 0 };
move_guide[2] = { 0, -1 };
move_guide[3] = { -1, 0 };
// 방문 표시
visited[now_x][now_y] = false;
// 경로 추가
route.push_back({ now_x, now_y });
for (int i = 0; i < 4; i++) {
// 다음 후보 인덱스
int next_x = now_x + move_guide[i][0];
int next_y = now_y + move_guide[i][1];
//// 후보 인덱스가 조건에 부합하면
// 인덱스 범위안에 존재하는지
// 방문한적 없는 인덱스인지
// 벽이 아닌지
if ((next_x >= 0 and next_x < N) and
(next_y >= 0 and next_y < M) and
(visited[next_x][next_y]) and
(map_arr[next_x][next_y] == 0)) {
DFS_array_reculsion(map_arr, visited, N, M, next_x, next_y);
}
}
}
int main(void) {
// 격자의 크기, 행 / 열
int N = 10;
int M = 10;
// 맵 생성, 0 : 길 / 1 : 벽
array<array<int, 10>, 10> map_arr;
map_arr[9] = { 1, 0, 1, 1, 0, 0, 0, 1, 0, 0 };
map_arr[8] = { 0, 0, 1, 1, 0, 1, 0, 0, 0, 1 };
map_arr[7] = { 1, 0, 0, 1, 0, 1, 1, 0, 1, 1 };
map_arr[6] = { 0, 0, 0, 1, 1, 0, 0, 0, 1, 0 };
map_arr[5] = { 1, 1, 0, 1, 0, 1, 1, 0, 1, 0 };
map_arr[4] = { 0, 0, 0, 1, 0, 1, 0, 0, 0, 0 };
map_arr[3] = { 1, 1, 0, 0, 0, 0, 0, 1, 1, 0 };
map_arr[2] = { 1, 1, 0, 1, 0, 1, 0, 0, 1, 1 };
map_arr[1] = { 1, 0, 0, 1, 0, 0, 1, 0, 1, 0 };
map_arr[0] = { 0, 0, 1, 0, 0, 1, 1, 1, 1, 0 };
// 방문 목록
array<array<bool, 10>, 10> visited;
// 방문 목록 true 로 초기화
for (int i = 0; i < N; i++) visited[i].fill(true);
// 함수 실행
DFS_array_reculsion(map_arr, visited, N, M, 0, 0);
cout << "[ ";
for (auto arr : route) {
cout << "[ " << arr[0] << " " << arr[1] << " ] ";
}
cout << "]\n";
}[ Python, list, stack]
더보기
# visited list + stack
def DFS_listay_stack(map_list, N, M):
# 이동 가이드, 4 방향
move_guide = [[] for _ in range(4)]
move_guide[0] = [ 0, 1 ]
move_guide[1] = [ 1, 0 ]
move_guide[2] = [ 0, -1 ]
move_guide[3] = [ -1, 0 ]
# 모든 이동경로 기록
routes = []
# 스택
stk = [[0, 0]]
# 방문 목록
visited = [[True for _ in range(10)] for __ in range(10)]
# 스택이 빌 때 까지 탐색
while not stk:
# 현재 인덱스
now_x = stk[-1][0]
now_y = stk[-1][1]
# 방문 기록
visited[now_x][now_y] = False
# 이동경로 기록
routes.append([ now_x, now_y ])
# 이동 가이드를 따라 네방향 탐색
for i in range(4):
# 다음 후보 인덱스
next_x = now_x + move_guide[i][0]
next_y = now_y + move_guide[i][1]
## 후보 인덱스가 조건에 부합하면
# 인덱스 범위안에 존재하는지
# 방문한적 없는 인덱스인지
# 벽이 아닌지
if (next_x >= 0 and next_x < N) and \
(next_y >= 0 and next_y < M) and \
(visited[next_x][next_y]) and \
(map_list[next_x][next_y] == 0):
# 스택에 삽입
stk.append([ next_x, next_y ])
# 바로 다음 인덱스 탐색
break
# 조건에 부합하는 후보 인덱스가 존재하지 않으면
elif i == 3:
# 스택에서 팝
stk.pop()
return routes
# 격자의 크기, 행 / 열
N = 10
M = 10
# 맵 생성, 0 : 길 / 1 : 벽
map_list = [[] for _ in range(10)]
map_list[9] = [ 1, 0, 1, 1, 0, 0, 0, 1, 0, 0 ]
map_list[8] = [ 0, 0, 1, 1, 0, 1, 0, 0, 0, 1 ]
map_list[7] = [ 1, 0, 0, 1, 0, 1, 1, 0, 1, 1 ]
map_list[6] = [ 0, 0, 0, 1, 1, 0, 0, 0, 1, 0 ]
map_list[5] = [ 1, 1, 0, 1, 0, 1, 1, 0, 1, 0 ]
map_list[4] = [ 0, 0, 0, 1, 0, 1, 0, 0, 0, 0 ]
map_list[3] = [ 1, 1, 0, 0, 0, 0, 0, 1, 1, 0 ]
map_list[2] = [ 1, 1, 0, 1, 0, 1, 0, 0, 1, 1 ]
map_list[1] = [ 1, 0, 0, 1, 0, 0, 1, 0, 1, 0 ]
map_list[0] = [ 0, 0, 1, 0, 0, 1, 1, 1, 1, 0 ]
print(DFS_listay_stack(map_list, N, M))[ Python, list, 재귀]
더보기
# visited ilst + reculsion
def DFS_array_reculsion(map_list, visited, N, M, now_x, now_y):
# 이미 방문한 노드면 종료
if not visited[now_x][now_y]: return
# 이동 가이드, 4 방향
move_guide = [[] for _ in range(4)]
move_guide[0] = [ 0, 1 ]
move_guide[1] = [ 1, 0 ]
move_guide[2] = [ 0, -1 ]
move_guide[3] = [ -1, 0 ]
# 방문 표시
visited[now_x][now_y] = False
# 경로 추가
route.append([ now_x, now_y ])
for i in range(4):
# 다음 후보 인덱스
next_x = now_x + move_guide[i][0]
next_y = now_y + move_guide[i][1]
## 후보 인덱스가 조건에 부합하면
# 인덱스 범위안에 존재하는지
# 방문한적 없는 인덱스인지
# 벽이 아닌지
if (next_x >= 0 and next_x < N) and \
(next_y >= 0 and next_y < M) and \
(visited[next_x][next_y]) and \
(map_list[next_x][next_y] == 0):
DFS_array_reculsion(map_list, visited, N, M, next_x, next_y)
# 격자의 크기, 행 / 열
N = 10
M = 10
# 맵 생성, 0 : 길 / 1 : 벽
map_list = [[] for _ in range(10)]
map_list[9] = [ 1, 0, 1, 1, 0, 0, 0, 1, 0, 0 ]
map_list[8] = [ 0, 0, 1, 1, 0, 1, 0, 0, 0, 1 ]
map_list[7] = [ 1, 0, 0, 1, 0, 1, 1, 0, 1, 1 ]
map_list[6] = [ 0, 0, 0, 1, 1, 0, 0, 0, 1, 0 ]
map_list[5] = [ 1, 1, 0, 1, 0, 1, 1, 0, 1, 0 ]
map_list[4] = [ 0, 0, 0, 1, 0, 1, 0, 0, 0, 0 ]
map_list[3] = [ 1, 1, 0, 0, 0, 0, 0, 1, 1, 0 ]
map_list[2] = [ 1, 1, 0, 1, 0, 1, 0, 0, 1, 1 ]
map_list[1] = [ 1, 0, 0, 1, 0, 0, 1, 0, 1, 0 ]
map_list[0] = [ 0, 0, 1, 0, 0, 1, 1, 1, 1, 0 ]
# 이동 경로
route = []
# 방문 목록
visited = [[True for _ in range(10)] for __ in range(10)]
# 함수 실행
DFS_array_reculsion(map_list, visited, N, M, 0, 0)
print(route)
728x90