[이것이코딩테스트다] CH05. DFS/BFS
그래프를 탐색하기 위한 대표적인 두 가지 알고리즘
1) 꼭 필요한 자료구조 기초
탐색이란, 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미함
DFS와 BFS를 제대로 이해하기 위해서는 스택과 큐에 대한 이해가 전제되어야 하므로, 이를 간단하게 정리하고 넘어가겠습니다.
스택(Stack)
박스 쌓기에 비유할 수 있으며, 선입후출입니다.
큐(Queue)
대기 줄에 비유할 수 있므녀, 선입선출입니다.
재귀함수
DFS와 BFS를 구현하기 위해서는 해당 개념에 대한 이해도 필요합니다.
재귀 함수란, 자기 자신을 다시 호출하는 함수를 의미합니다.
이때 무한하게 자기자신을 호출해서는 안되겠죠?
따라서 재귀함수는 종료 조건이 존재해야합니다.
1 2 3 4 5 6 7 8 9 10 11 | def recursive_function(i): #100번째의 출력 때 종료되도록 조건 명시 if i == 100: return print(i, "번째 재귀 함수에서", i+1, "번째 재귀 함수를 호출합니다.") recursive_function(i+1) print(i, "번째 재귀함수를 종료함") recursive_function(1) | cs |
함수가 반복적으로 호출될 때, 가장 마지막에 호출된 함수가 먼저 수행되어야 그 앞의 함수 호출이 종료됩니다.
즉 스택 자료구조형과 일치하죠? 내부적으로 동일하게 작동합니다.
스택 자료구조를 활용해야하는 상당수의 알고리즘이 재귀 함수를 이용해서 간편하게 구현될 수 있다고 하네요
팩토리얼 예제로 한번 더 정리하고 넘어갑시다
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | #단순 반복으로 구현한 n! def factorial_iterative(n): result = 1 #1부터 n까지의 수를 차례대로 곱한다 for i in range(1, n+1): result *= i return result #재귀로 구현한 n! def factorial_recursive(n): if n <= 1: return 1 return n * factorial_recursive(n-1) | cs |
1. $n$이 0, 1일 때 $factorial(n) = 1$
2. $n$이 1보다 클 때 $factorial(n)=n \times factorial(n-1)$
위 팩토리얼의 수학적 점화식의 형태를 유지하면서 코드를 작성할 수 있다는 장점이 있습니다.
2) 탐색 알고리즘 DFS/BFS
DFS (Depth-First Search)
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
이를 프로그래밍적으로 표현하는 2가지 방법이 존재한다.
먼저, 그래프를 인접 행렬로 표현하는 방식
# 2차원 리스트를 이용해 인접 행렬 표현
INF = 9999999999
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 8]
]
그리고 그래프를 인접 리스트 방식으로 저장하는 방식
이때 인접 리스트는 연결 리스트 자료구조를 이용해 구현한다.
#행이 3개인 2차원 리스트로 인접 리스트를 표현
graph = [[]for _ in range(3)]
#노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))
#노드1, 2도 append(생략함)
DFS는 특정 경로로 탐색하다가, 특정한 상황에서 최대한 깊숙하게 들어가서 노드를 방문한 뒤, 다시 돌아가서 다른 경로로 탐색하는 알고리즘이다.
구체적인 동작 과정은 아래와 같다
1. 탐색 시작 노드를 Stack에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면, 해당 노드를 Stack에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없는 경우 스택에서 최상단 노드를 꺼낸다.
3. (2)의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
위와 같은 그래프에서 노드 1을 시작 노드로 탐색한다고 할 때,
노드의 탐색 순서(스택에 들어간 순서)는
1 > 2 > 7 > 6 > 8 > 3 > 4> 5
탐색을 수행함에 있어서 $O(N)$의 시간이 소요된다는 특징이 있음
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트) - 일부 생략
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5]
]
# 각 노드가 방문한 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False]*9
#DFS 메서드 정의
def dfs(graph, v, visited):
#현재 노드를 방문 처리함
visited[v] = true
print(v, end=' ')
#현재 노드와 연결된 다른 노드를 재귀적으로 방문함
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
#호출
dfs(graph, 1, visited)
BFS(Breadth First Search)
BFS는 너비 우선 탐색으로, 가까운 노드부터 탐색하는 알고리즘이다.
선입선출 방식인 큐를 이용하여, 인접한 노드를 반복해서 큐에 넣으면 먼저 들어간 것이 나가게 됩니다.
동작 방식은
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 시작 노드를 꺼내, 해당 노드의 인접 노드 중에서 방문하지 않는 노드를 모두 큐에 삽입하고 방문 처리
3. (2)의 과정을 더 이상 수행할 수 없을 때까지 반복
마찬자리고 해당 그래프에서 노드 1을 시작 노드로 설정하고 탐색하면,
노드의 탐색 순서(큐에 들어간 순서)는
1 > 2 > 3 > 8 > 7 > 3 > 5 > 6
탐색을 수행함에 있어서 $O(N)$의 시간이 소요된다는 특징이 있음
재귀 함수로 DFS를 구현하면 실제 프로그램의 수행 시간은 조금 느려질 수 있습니다.
보통 DFS보다는 BFS 구현이 조금 더 빠르게 동작합니다.
from collections import deque
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트) - 일부 생략
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5]
]
# 각 노드가 방문한 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False]*9
#DFS 메서드 정의
def bfs(graph, start, visited):
#큐 구현을 위해서 deque 라이브러리 사용
queue = deque([start])
#현재 노드를 방문 처리함
visited[start] = true
#큐가 빌 때까지 반복함
while queue:
#큐에서 하나의 원소를 뽑아 출력
v = queue.popleft()
print(v, end=' ')
#해당 원소와 연결되어있고, 아직 방문하지 않은 원소들을 큐에 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = true
#호출
bfs(graph, 1, visited)
이런 DFS, BFS 유형의 경우 1차원 배열이나 2차원 배열을 그래프 형식으로 생각하면 문제가 쉽게 풀리는 경우가 있다!
예제 1) 음료수 얼려먹기
<생각>
좌표 (0, 0) 부터 방문하면서
주변의 구멍을 모두 visit한다.
이미 visit 처리 된 경우는 다음 좌표로 넘어가면서, (N-1, N-1)까지 확인
↓ My code ↓
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | //음료수 얼려먹기 #include <iostream> using namespace std; int N, M; int ice[1000][1000]; int visited[1000][1000] = { false, }; int BFS(int i, int j) { if (i < 0 || i >= N || j < 0 || j >= M) return; visited[i][j]; for (int dx = -1; dx <= 1; dx++) { for (int dy = -1; dy <= 1; dy++) { if ((i + dx > 0 && i + dx < N) && (i + dy > 0 && i + dy < M)) BFS(i + dx, i + dy); } } } int main() { cin >> N >> M; int num; for (int i=0; i<N; i++) for (int j = 0; j < M; j++) { ice[i][j] = num; } } | cs |
근데 얼음이 생겼다고 어떻게 세지..? 하고 끝냈다.
실제로 테스트를 돌려본 코드가 아니고 머리로 생각한 코드임
<생각하지 못한 부분>
현재 노드를 아직 방문하지 않았다면, 재귀적으로 호출하여 확인하고 return하면 되는 것이었음
그리고 2차원 리스트 맵 입력 받을 때 scanf("%1d", &graph[i][j])하는 것도 깔끔하군
그리고 종료 조건도 잘 확인하기..
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #include <iostream> using namespace std; int n, m; int graph[1000][1000]; // DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문 bool dfs(int x, int y) { // 주어진 범위를 벗어나는 경우에는 즉시 종료 if (x <= -1 || x >= n || y <= -1 || y >= m) { return false; } // 현재 노드를 아직 방문하지 않았다면 if (graph[x][y] == 0) { // 해당 노드 방문 처리 graph[x][y] = 1; // 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출 dfs(x - 1, y); dfs(x, y - 1); dfs(x + 1, y); dfs(x, y + 1); return true; } return false; } int main() { // N, M을 공백을 기준으로 구분하여 입력 받기 cin >> n >> m; // 2차원 리스트의 맵 정보 입력 받기 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%1d", &graph[i][j]); } } // 모든 노드(위치)에 대하여 음료수 채우기 int result = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // 현재 위치에서 DFS 수행 if (dfs(i, j)) { result += 1; } } } cout << result << '\n'; // 정답 출력 } | cs |
예제 2) 미로탈출
<생각>
위의 코드와 동일한 원리라고 생각했고,
parameter에 이동한 칸의 수를 세서 탈출을 위한 최소 칸의 개수를 세려고 했다.
↓ My code ↓
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | // p152 미로 탈출 #define _CRT_SECURE_NO_WARNINGS #include <iostream> using namespace std; int N, M; int escape[200][200]; bool visited[200][200] = { false, }; int minMove; void DFS(int i, int j, int num) { if (i <= -1 || i >= N || j <= -1 || j >= M || visited[i][j] == true) return; if (escape[i][j] == 0) { cout << "괴물이 있어" << i << ", " << j << "\n"; return; } if (i == N-1 && j == M-1) { cout << "도착한 시점의 min Move는 " << minMove << ", num은 " << num << "\n"; if (minMove > num) minMove = num; return; } visited[i][j] = true; cout << "현재 " << i << ", " << j << "\n"; DFS(i - 1, j, num + 1); DFS(i + 1, j, num + 1); DFS(i, j - 1, num + 1); DFS(i, j + 1, num + 1); return; } int main() { cin >> N >> M; for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) { scanf("%1d", &escape[i][j]); } minMove = N * M; DFS(0, 0, 1); cout << minMove; } | cs |
당연히 DFS로 풀었는데, 풀이를 보니까 BFS로 풀었군 ...
확인하러 갑시다
<생각하지 못한 부분>
BFS로 풀기ㅎㅎ... 역시 익숙한 것만 찾는 나
아래 답에서 상하좌우 탐색하는 방식도 단순해서 좋은 것 같다! 기억하기
해당 문제는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문에 BFS로 풀었을 때 효과적입니다.
기준 노드에서 상하좌우를 확인하고,
이동 가능하면(처음 방문 하면) 기준 노드에 적혀있는 이동 단위 + 1를 기록해줌
이후 queue에 넣고 그 주변 노드도 확인
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | int n, m; int graph[201][201]; // 이동할 상하좌우 int dx[] = { -1, 1, 0, 0 }; int dy[] = { 0, 0, -1, 1 }; int bfs(int x, int y) { // Queue 구현을 위한 queue 라이브러리 사용 queue<pair<int, int>> q; q.push({ x, y }); // Queue가 빌 때까지 반복함 while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); // 현재 위치에서 4가지 방향으로의 위치를 확인 for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; // 미로 공간을 벗어난 경우는 무시함 if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 괴물이 있는 경우 무시함 if (graph[nx][ny] == 0) continue; // 해당 노드를 처음 방문하는 경우에만 최단 거리 기록 if (graph[nx][ny] == 1) { graph[nx][ny] = graph[x][y] + 1; q.push({ nx, ny }); } } } // 가장 오른쪽 아래까지의 최단 거리를 반환 return graph[n - 1][m - 1]; } int main(void) { // N, M을 공백을 기준으로 구분하여 입력 받기 cin >> n >> m; // 2차원 리스트의 맵 정보 입력 받기 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%1d", &graph[i][j]); } } // BFS를 수행한 결과 출력 cout << bfs(0, 0) << '\n'; return 0; } | cs |