접근
- graph 또는 tree를 탐색하는 알고리즘이다.
- 특정 노드부터 시작하여 최대한 멀리 갈 수 있을만큼 진행한다.
- 바로 전 분기점까지 돌아가고 아직 방문하지 않은 다음 노드로 진행한다. (방문한 노드들은 표시한다)
알고리즘
- 재귀함수를 사용한다.
- 현재 노드를 visit 했다고 표시한다.
- 인접해있고 visit하지 않은 노드를 탐색하고 해당 노드의 index를 넣은 재귀함수를 호출한다.
Pseudo-code
dfs(current){
visited[current] = true;
for(adj){
if(!visited[adj])
dfs(adj);
}
}
적용
https://jolly-note.tistory.com/61
[백준/baekjoon] Silver4 1388. 바닥 장식
DFS -DFS 링크 추가 예정- 더보기 #include #include using namespace std; int x, y; vector > map; vector > visited; int dfs(int i, int j) { visited[i][j] = true; if (map[i][j] == '|') { if (i + 1 == x..
jolly-note.tistory.com
https://jolly-note.tistory.com/64
[SW Expert Academy] Lv.3 1244. 최대 상금
my full code #include #include #include using namespace std; int answer = -1; void dfs(string res, int ch) { if (is_sorted(res.rbegin(), res.rend())) { string u_res(res); auto it = unique(u_res.begi..
jolly-note.tistory.com
https://jolly-note.tistory.com/65
[백준/baekjoon] Silver3 2606. 바이러스
DFS 연습 2일차 DFS 재밌네 더보기 #include #include using namespace std; vector visited; vector > adj; int cnt = 0; void dfs(int current) { visited[current] = true; for (int a : adj[current]) { if (v..
jolly-note.tistory.com
https://jolly-note.tistory.com/69
[programmers] Lv.2 타겟 넘버(c++)
DFS, BFS 두 방법으로 풀었다. (BFS는 나중에 추가 예정) my full code #include using namespace std; int answer=0; void dfs(vector & numbers, int& target, int idx, int num){ if(idx+1 == numbers.size()+1..
jolly-note.tistory.com
https://jolly-note.tistory.com/70
[programmers] Lv.3 네트워크(c++)
DFS에 대한 두려움이 많이 줄어든것같다. my full code #include #include using namespace std; void dfs(vector >& computers, int i){ computers[i][i] = 0; for(int k=0; k > computers) { int answer = 0; fo..
jolly-note.tistory.com
https://jolly-note.tistory.com/71?category=1025701
[백준/baekjoon] Silver1 2667. 단지번호붙이기
DFS 연습용으로 들어갔는데 예전에 BFS로 풀었던 것이랑 비슷한 문제(👇)여서 https://jolly-note.tistory.com/43 visit; int nb_area; vector x_dir; vector y_dir; int find_area(int i, int j, vector > pictur..
jolly-note.tistory.com
https://jolly-note.tistory.com/72
[백준 && SW] gold5/D3 N-Queen
백준과 SW Expert Academy 양쪽에 있는 문제이다. 수업에서도 들었던 기억이 있다. 더보기 // 같은 행과 열에 하나씩 들어갈 수 있음 // 대각선인지만 확인하면됨. 같은 x좌표끼리의 차이와 y좌표끼리
jolly-note.tistory.com
참고
https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/
Depth First Search or DFS for a Graph - GeeksforGeeks
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
www.geeksforgeeks.org
'note > algorithm' 카테고리의 다른 글
| BFS (Breadth First Search, 너비 우선 탐색) (0) | 2022.05.22 |
|---|---|
| linked list - 이중(doubly) 연결 리스트(c++) (0) | 2022.04.27 |
댓글