-
[C++] DFS(Depth First Search) ๊น์ด ์ฐ์ ํ์ ์๊ณ ๋ฆฌ์ฆAlgorithm & Data Structure 2022. 1. 30. 15:19๋ฐ์ํ
๋ค์ด๊ฐ๋ฉฐ
DFS๋ ์์์ ๋ฐฐ์ด BFS์ฒ๋ผ ํ์ ์๊ณ ๋ฆฌ์ฆ ์ค ํ๋์ด๋ค. BFS์ ๊ตฌํ์ ์ฐจ์ด์ ์ด ์๋ค๋ฉด BFS์์๋ Queue(ํ)๋ฅผ ์ฌ์ฉ ํ์ง๋ง, DFS์์๋ Stack(์คํ)์ ์ฌ์ฉํด์ ๊ตฌํํ๋ค.
DFS(๊น์ด ์ฐ์ ํ์) ์ด๋?
๊น์ด ์ฐ์ ํ์( - ๅชๅ ๆข็ดข, ์์ด: depth-first search, DFS)์ ๋งน๋ชฉ์ ํ์๋ฐฉ๋ฒ์ ํ๋๋ก ํ์ํธ๋ฆฌ์ ์ต๊ทผ์ ์ฒจ๊ฐ๋ ๋ ธ๋๋ฅผ ์ ํํ๊ณ , ์ด ๋ ธ๋์ ์ ์ฉ ๊ฐ๋ฅํ ๋์์ ์ค ํ๋๋ฅผ ์ ์ฉํ์ฌ ํธ๋ฆฌ์ ๋ค์ ์์ค(level)์ ํ ๊ฐ์ ์์๋ ธ๋๋ฅผ ์ฒจ๊ฐํ๋ฉฐ, ์ฒจ๊ฐ๋ ์์ ๋ ธ๋๊ฐ ๋ชฉํ๋ ธ๋์ผ ๋๊น์ง ์์ ์์ ๋ ธ๋์ ์ฒจ๊ฐ ๊ณผ์ ์ ๋ฐ๋ณตํด ๊ฐ๋ ๋ฐฉ์์ด๋ค.
- ์ํค๋ฐฑ๊ณผDFS ์๊ณ ๋ฆฌ์ฆ
์๋์ ์ฌ์ง๋ค์ ๋ณด๊ณ DFS๋ฅผ ์ดํดํด๋ณด์.
์์ ์ง์ ์ 1์ด๋ผ๊ณ ํ์. 1์ ๋ฐฉ๋ฌธํ๋ค๋ ํ์๋ฅผ ๋จ๊ธฐ๊ณ ํด๋น ์นธ์ ์คํ์ ๋ฃ๋๋ค. ๊ทธ๋ฆฌ๊ณ ์คํ์ top์ popํ๊ณ popํ ์นธ์ ์ฃผ๋ณ(์ํ์ข์ฐ)์ ํ์ํ์ฌ ๋ฐฉ๋ฌธํ์ง ์์๋ค๋ฉด ์คํ์ ๋ฃ๋๋ค.
์คํ์ top์ธ 1์ pop ํ์ผ๋ฏ๋ก 1์ ์ฃผ๋ณ์ธ 2์ 3์ ํ์ํ์ฌ ๋ฐฉ๋ฌธํ๋ค๋ ํ์๋ฅผ ๋จ๊ธฐ๊ณ ์คํ์ ๋ฃ๋๋ค.
์คํ์ top์ธ 3์ pop ํ์ผ๋ฏ๋ก 3์ ์ฃผ๋ณ์ธ 6๊ณผ 7์ ํ์ํ์ฌ ๋ฐฉ๋ฌธํ๋ค๋ ํ์๋ฅผ ๋จ๊ธฐ๊ณ ์คํ์ ๋ฃ๋๋ค.
์คํ์ top์ธ 7์ pop ํ์ง๋ง ์ฃผ๋ณ์ ํ์ํ ๊ฒ์ด ์์ด์ ๋๊ธด๋ค. ๊ทธ๋ฆฌ๊ณ ๋ค์ ์คํ์ top์ธ 6 ๋ํ ํ์ํ ๊ฒ์ด ์์ผ๋ฏ๋ก ๋๊ธด๋ค. ๊ทธ๋ฆฌ๊ณ ์คํ์ top์ธ 2๋ฅผ pop ํ์ผ๋ฏ๋ก 2์ ์ฃผ๋ณ์ธ 4์ 5๋ฅผ ํ์ํ์ฌ ๋ฐฉ๋ฌธํ๋ค๋ ํ์๋ฅผ ๋จ๊ธฐ๊ณ ์คํ์ ๋ฃ๋๋ค.
์คํ์ top์ธ 5๋ฅผ pop ํ์ผ๋ฏ๋ก 5์ ์ฃผ๋ณ์ธ 9๋ฅผ ํ์ํ์ฌ ๋ฐฉ๋ฌธํ๋ค๋ ํ์๋ฅผ ๋จ๊ธฐ๊ณ ์คํ์ ๋ฃ๋๋ค.
์คํ์ top์ธ 9๋ฅผ pop ํ์ง๋ง ์ฃผ๋ณ์ ํ์ํ ๊ฒ์ด ์์ด์ ๋๊ธด๋ค. ๋ค์ ์คํ์ top์ธ 4๋ฅผ pop ํ์ผ๋ฏ๋ก 4์ ์ฃผ๋ณ์ธ 8์ ํ์ํ์ฌ ๋ฐฉ๋ฌธํ๋ค๋ ํ์๋ฅผ ๋จ๊ธฐ๊ณ ์คํ์ ๋ฃ๋๋ค.
์คํ์ top์ธ 8์ pop ํ์ง๋ง ์ฃผ๋ณ์ ํ์ํ ๊ฒ์ด ์์ด์ ๋๊ธด๋ค. ์คํ์ด ๋น์์ผ๋ฏ๋ก DFS๊ฐ ๋๋ฌ๋ค.
DFS ๋ฌธ์ ํด๊ฒฐ
- ์์ํ๋ ์นธ์ ๋ฐฉ๋ฌธํ๋ค๋ ํ์๋ฅผ ํ๊ณ ์คํ์ ๋ฃ๋๋ค.
- ์คํ์ top์ ์๋ ์์๋ฅผ ๊บผ๋ด์ด(pop) ๊ทธ ์์์ ์ฃผ๋ณ(์ํ์ข์ฐ)์ ํ์ํ๋ค. ๋ง์ฝ ํด๋น ์นธ์ ์ด์ ์ ๋ฐฉ๋ฌธํ๋ค๋ฉด ๋์ด๊ฐ๊ณ , ์ฒ์์ผ๋ก ๋ฐฉ๋ฌธํ๋ค๋ฉด ๋ฐฉ๋ฌธํ๋ค๋ ํ์๋ฅผ ๋จ๊ธฐ๊ณ ํด๋น ์นธ์ ์คํ์ ๋ฃ๋๋ค.
- ์คํ์ด ๋น ๋๊น์ง ๊ณ์ํด์ 2๋ฒ์ ๋ฐ๋ณตํ๋ค.
* ๋ชจ๋ ์นธ์ ์คํ์ 1๋ฒ์ฉ ๋ค์ด๊ฐ๋๊น DFS ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ ๋ณต์ก๋๋ ์นธ์ด n๊ฐ๋ผ๋ฉด O(n)์ด๋ค.
์๋์ ์ฝ๋๋ DFS๋ฅผ ์ดํดํ ์ ์๋ ์ฝ๋์ด๋ค.
#include <bits/stdc++.h> using namespace std; #define X first // pair์์ first ๋ฅผ ์ค์ฌ ์ฐ๊ธฐ ์ํด #define Y second // pair์์ 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]; // ํด๋น ์นธ์ ๋ฐฉ๋ฌธํ๋์ง์ ์ฌ๋ถ๋ฅผ ์ ์ฅ int n = 7, m = 10; // n = ํ์ ์, m = ์ด์ ์ int dx[4] = { 1, 0, -1, 0 }; // ์ํ์ข์ฐ 4๊ฐ์ ๋ฐฉํฅ์ ์๋ฏธ int dy[4] = { 0, 1, 0, -1 }; // ์ํ์ข์ฐ 4๊ฐ์ ๋ฐฉํฅ์ ์๋ฏธ 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}); while (!S.empty()) { pair<int, int> cur = S.top(); // ์์์ ์ฃผ๋ณ์ ํ์ํ๊ธฐ ์ํด cur๋ฅผ ์ฌ์ฉํ๋ค. S.pop(); // ์คํ์ top์ ์๋ ์์๋ฅผ ๊บผ๋ธ๋ค. cout << '(' << cur.X << ", " << cur.Y << ") -> "; for (int dir = 0; dir < 4; dir++) { // ์ํ์ข์ฐ ์นธ์ ํ์ํ๋ค. int nx = cur.X + dx[dir]; // nx์ dir์์ ์ ํ ๋ฐฉํฅ(์ํ์ข์ฐ)์ ์ธ์ ํ ์นธ์ ์ขํ๊ฐ ๋ค์ด๊ฐ๋ค. int ny = cur.Y + dy[dir]; // ny์ dir์์ ์ ํ ๋ฐฉํฅ(์ํ์ข์ฐ)์ ์ธ์ ํ ์นธ์ ์ขํ๊ฐ ๋ค์ด๊ฐ๋ค. if (nx < 0 || nx >= n || ny < 0 || ny >= m) { continue; // ๋ฒ์๋ฅผ ๋ฒ์ด๋ ๊ฒฝ์ฐ์๋ ๋์ด๊ฐ๋ค. } if (vis[nx][ny] || board[nx][ny] != 1) { continue; // ์ด๋ฏธ ๋ฐฉ๋ฌธํ ์นธ์ด๊ฑฐ๋ ๋ฐฉ๋ฌธํ ํ์๊ฐ ์๋(๋นจ๊ฐ ์นธ)์ผ ๊ฒฝ์ฐ ๋์ด๊ฐ๋ค. } vis[nx][ny] = 1; // (nx, ny) ์ขํ๋ฅผ ๋ฐฉ๋ฌธํ๋ค๊ณ ํ์ํ๋ค. S.push({nx, ny}); // ํด๋น ์นธ์ ์คํ์ ๋ฃ๋๋ค. } } return 0; }
๋ฐ์ํ