๐ ๊ณต๋ถํ๋ ์ง์ง์ํ์นด๋ ์ฒ์์ด์ง?
[์ด๊ฒ์ด ์ฝ๋ฉ ํ ์คํธ๋ค with Python]_18_DFS ๋ณธ๋ฌธ
[์ด๊ฒ์ด ์ฝ๋ฉ ํ ์คํธ๋ค with Python]_18_DFS
์ง์ง์ํ์นด 2022. 2. 2. 01:03220202 ์์ฑ
<๋ณธ ๋ธ๋ก๊ทธ๋ ใ์ด๊ฒ์ด ์ทจ์ ์ ์ํ ์ฝ๋ฉ ํ ์คํธ๋คใ ์ youtube๋ฅผ ์ฐธ๊ณ ํด์ ๊ณต๋ถํ๋ฉฐ ์์ฑํ์์ต๋๋ค>
https://www.youtube.com/watch?v=1vLqC1rItM8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=18
1. DFS (Depth-First Search)
: ๊น์ด ์ฐ์ ํ์
: ๊ทธ๋ํ์์ ๊น์ ๋ถ๋ถ์ ์ฐ์ ์ ์ผ๋ก ํ์
: ์คํ ์๋ฃ๊ตฌ์กฐ ( ์ฌ๊ทํจ์ ) ์ด์ฉ
1) ํ์ ์์ ๋ ธ๋๋ฅผ ์คํ์ ์ฝ์ , ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ ํจ
2) ์คํ์ ์ต์๋จ ๋ ธ๋์ ๋ฐฉ๋ฌธํ์ง ์์ ์ธ์ ํ ๋ ธ๋๊ฐ ํ๋๋ผ๋ ์์ผ๋ฉด ๊ทธ ๋ ธ๋๋ฅผ ์คํ์ ๋ฃ๊ณ ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ
( ๋ฐฉ๋ฌธํ์ง ์์ ์ธ์ ๋ ธ๋ ์์ผ๋ฉด ์คํ์์ ์ต์๋จ ๋ ธ๋ ๊บผ๋ด๊ธฐ)
3) 2๋ฒ ๊ณผ์ ์ ์ํํ ์ ์์ ๋๊น์ง ๋ฐ๋ณต
+) ๋์ ์์
- ์์ ๋ ธ๋ 1
: ๋ฒํธ๊ฐ ๋ฎ์ ์ธ์ ๋ ธ๋๋ถํฐ ! ๋ฐฉ๋ฌธ
- 2, 3, 8 ์ค์์ ๊ฐ์ฅ ์์ ๋ ธ๋์ธ 2๋ฅผ ์คํ์ ๋ฃ๊ณ ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ !
- 2์ ๋ฐฉ๋ฌธํ์ง ์์ ์ธ์ ๋ ธ๋ 7์ ์คํ์ ๋ฃ๊ณ ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ !
- 8, 6 ์ค์์ ๊ฐ์ฅ ์์ ๋ ธ๋์ธ 6์ ์คํ์ ๋ฃ๊ณ ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ !
- 6์์ ๋์ด์ ๊น์ด์ง ๊ณณ์ด ์๋ค ! 6์ ๋นผ๋ผ !
- 7 ์์ ์ ๊ฐ๋ณธ... 8์ ๊ฐ๋ณด์ !!!
- 8 ์ 1 ๋ฐ์ ์์ฆ!! 1์ ์ด๋ฏธ ํ์ผ๋ฏ๋ก 3์ ๊ฐ๋น
- 4, 5, ์ค ๊ฐ์ฅ ์์ ๋ ธ๋์ธ 4 !
- ๊ทธ๋ค์ ๋ง์ง๋ง 5 !
=> 1, 2, 7, 6, 8, 3, 4, 5
- python
def dfs(graph, v, visited) :
# ํ์ฌ ๋
ธ๋๋ฅผ ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ
visited[v] = True
print(v, end = " ")
# ํ์ฌ ๋
ธ๋์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ๋
ธ๋๋ฅผ ์ฌ๊ท์ ๋ฐฉ๋ฌธ
for i in graph[v] :
if not visited[i] :
dfs(graph, i, visited)
# ๊ฐ ๋
ธ๋๊ฐ ์ฐ๊ฒฐ๋ ์ ๋ณด ํํ ( 2์ฐจ์ ๋ฆฌ์คํธ )
graph = [
[],
[2, 3, 5],
[1, 7],
[1, 4, 5],
[3, 4],
[3, 5],
[2, 5, 4],
[7],
[1, 7]
]
# ๊ฐ ๋
ธ๋๊ฐ ๋ฐฉ๋ฌธ๋ ์ ๋ณด ํํ ( 1์ฐจ์ ๋ฆฌ์คํธ )
visited = [False] * 9
dfs(graph, 1, visited)
# result
# 1 2 7 3 4 5
- c++
#include <bits/stdc++.h>
using namespace std;
bool visited[9];
vector<int> graph[9];
// DFS ํจ์ ์ ์
void dfs(int x) {
// ํ์ฌ ๋
ธ๋๋ฅผ ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ
visited[x] = true;
cout << x << ' ';
// ํ์ฌ ๋
ธ๋์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ๋
ธ๋๋ฅผ ์ฌ๊ท์ ์ผ๋ก ๋ฐฉ๋ฌธ
for (int i = 0; i < graph[x].size(); i++) {
int y = graph[x][i];
if (!visited[y]) dfs(y);
}
}
int main(void) {
// ๋
ธ๋ 1์ ์ฐ๊ฒฐ๋ ๋
ธ๋ ์ ๋ณด ์ ์ฅ
graph[1].push_back(2);
graph[1].push_back(3);
graph[1].push_back(8);
// ๋
ธ๋ 2์ ์ฐ๊ฒฐ๋ ๋
ธ๋ ์ ๋ณด ์ ์ฅ
graph[2].push_back(1);
graph[2].push_back(7);
// ๋
ธ๋ 3์ ์ฐ๊ฒฐ๋ ๋
ธ๋ ์ ๋ณด ์ ์ฅ
graph[3].push_back(1);
graph[3].push_back(4);
graph[3].push_back(5);
// ๋
ธ๋ 4์ ์ฐ๊ฒฐ๋ ๋
ธ๋ ์ ๋ณด ์ ์ฅ
graph[4].push_back(3);
graph[4].push_back(5);
// ๋
ธ๋ 5์ ์ฐ๊ฒฐ๋ ๋
ธ๋ ์ ๋ณด ์ ์ฅ
graph[5].push_back(3);
graph[5].push_back(4);
// ๋
ธ๋ 6์ ์ฐ๊ฒฐ๋ ๋
ธ๋ ์ ๋ณด ์ ์ฅ
graph[6].push_back(7);
// ๋
ธ๋ 7์ ์ฐ๊ฒฐ๋ ๋
ธ๋ ์ ๋ณด ์ ์ฅ
graph[7].push_back(2);
graph[7].push_back(6);
graph[7].push_back(8);
// ๋
ธ๋ 8์ ์ฐ๊ฒฐ๋ ๋
ธ๋ ์ ๋ณด ์ ์ฅ
graph[8].push_back(1);
graph[8].push_back(7);
dfs(1);
}
- java
import java.util.*;
public class Main {
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
// DFS ํจ์ ์ ์
public static void dfs(int x) {
// ํ์ฌ ๋
ธ๋๋ฅผ ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ
visited[x] = true;
System.out.print(x + " ");
// ํ์ฌ ๋
ธ๋์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ๋
ธ๋๋ฅผ ์ฌ๊ท์ ์ผ๋ก ๋ฐฉ๋ฌธ
for (int i = 0; i < graph.get(x).size(); i++) {
int y = graph.get(x).get(i);
if (!visited[y]) dfs(y);
}
}
public static void main(String[] args) {
// ๊ทธ๋ํ ์ด๊ธฐํ
for (int i = 0; i < 9; i++) {
graph.add(new ArrayList<Integer>());
}
// ๋
ธ๋ 1์ ์ฐ๊ฒฐ๋ ๋
ธ๋ ์ ๋ณด ์ ์ฅ
graph.get(1).add(2);
graph.get(1).add(3);
graph.get(1).add(8);
// ๋
ธ๋ 2์ ์ฐ๊ฒฐ๋ ๋
ธ๋ ์ ๋ณด ์ ์ฅ
graph.get(2).add(1);
graph.get(2).add(7);
// ๋
ธ๋ 3์ ์ฐ๊ฒฐ๋ ๋
ธ๋ ์ ๋ณด ์ ์ฅ
graph.get(3).add(1);
graph.get(3).add(4);
graph.get(3).add(5);
// ๋
ธ๋ 4์ ์ฐ๊ฒฐ๋ ๋
ธ๋ ์ ๋ณด ์ ์ฅ
graph.get(4).add(3);
graph.get(4).add(5);
// ๋
ธ๋ 5์ ์ฐ๊ฒฐ๋ ๋
ธ๋ ์ ๋ณด ์ ์ฅ
graph.get(5).add(3);
graph.get(5).add(4);
// ๋
ธ๋ 6์ ์ฐ๊ฒฐ๋ ๋
ธ๋ ์ ๋ณด ์ ์ฅ
graph.get(6).add(7);
// ๋
ธ๋ 7์ ์ฐ๊ฒฐ๋ ๋
ธ๋ ์ ๋ณด ์ ์ฅ
graph.get(7).add(2);
graph.get(7).add(6);
graph.get(7).add(8);
// ๋
ธ๋ 8์ ์ฐ๊ฒฐ๋ ๋
ธ๋ ์ ๋ณด ์ ์ฅ
graph.get(8).add(1);
graph.get(8).add(7);
dfs(1);
}
}
'๐ฆฅ ์ฝํ > ์ด๊ฒ์ด ์ฝ๋ฉ ํ ์คํธ๋ค with python' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์ด๊ฒ์ด ์ฝ๋ฉ ํ ์คํธ๋ค with Python]_20_DFS & BFS ๋ฌธ์ ํ์ด (0) | 2022.02.02 |
---|---|
[์ด๊ฒ์ด ์ฝ๋ฉ ํ ์คํธ๋ค with Python]_19_BFS (0) | 2022.02.02 |
[์ด๊ฒ์ด ์ฝ๋ฉ ํ ์คํธ๋ค with Python]_17_์ฌ๊ท ํจ์ (0) | 2022.02.02 |
[์ด๊ฒ์ด ์ฝ๋ฉ ํ ์คํธ๋ค with Python]_16_์คํ๊ณผ ํ (0) | 2022.02.02 |
[์ด๊ฒ์ด ์ฝ๋ฉ ํ ์คํธ๋ค with Python]_15_๊ตฌํ ๋ฌธ์ ํ์ด (0) | 2022.01.31 |