DFS 원형 -> 2022.9.23 확인
+ 2022.9.23 확인 & 수정+
#include <iostream>
#define N 7
int g[N][N] = {
{0,1,0,0,0,1,1},
{1,0,1,1,0,0,0},
{0,1,0,0,1,0,0},
{0,1,0,0,0,0,0},
{0,0,1,0,0,0,0},
{1,0,0,0,0,0,1},
{1,0,0,0,0,1,0}
};
int check[N];
void dfs(int here) {
//현재 지점을 방문한 점이 있다면 종료
if (check[here]) return;
//아니라면 방문하고 출력
check[here] = 1;
printf("정점 %d를 방문\n", here);
//변수 here는 노드에 적인 숫자 (0~6) 이 됨
for (int next = 0; next < N; next++)
//그래프가 이어져있으며, 다음 노드를 방문한 적이 없다면 dfs(next)
if (g[here][next] == 1 && !check[next]) dfs(next);
//0(node number)이랑 1(node number)이랑 이어져 있니?
//0이랑 2랑 이어져 있니?
//0이랑 3이랑 이어져 있니?
// ...
//0이랑 N-1이랑 이어져 있니?
//이 중 이어져 있니 ->ㅇㅇ 이 되는 순간 dfs(next)로 가서
//그 이어져 있는 노드에서 다시 다른 노드들과 이어져있는지 물어봄
}
int main() {
dfs(0);
}
일단 코드의 문제 -> for문에서 dfs 들어갈 때 visit 확인하면서 dfs 들어가고나서도 visit 확인함
N은 노드의 개수, here은 노드에 적힌 숫자 ( : 0 ~ N-1)
for문 부분이 노드를 (0 ~ N-1)까지 오름차순으로 dfs를 진행할 수 있게 해 준다
dfs에서 if문에 현재 지점을 방문한 적이 있다면~ 부분은
단순히 here = 0으로 생각하면 왜 있나 할텐데
재귀를 이용했으므로 dfs(next) 를 실행할 때
next에 따라 dfs에 전달해주는 변수의 값이 바뀌므로
이 부분 꼭 확인해주기! (dfs 응용 문제에서)
사실 재귀를 쓰는 함수는 들어오는 입력의 값이 어떻게 바뀔 수 있는지 꼭 확인해 줘야 하는 게 맞는듯..
if 문에서 현재 노드와 다음 탐색할 노드가 이어져 있는지 물어본 다음
이어져 있으면 바로 다음 노드로 들어가 탐색을 진행하는 것이 바로 DFS의 핵심!
더 깊은 곳이 있으면 현재 노드(here)한테 물어보는 거 그만하고 바로 깊은 곳으로 들어가~
?의문점
if 문에서 here를 포함시켜서 이어져있냐고 물어보는 부분..
일반 이차원 배열같은 경우 다중 그래프( multigraph : 두 꼭짓점 사이에 여러 변이 허용되는, 그래프의 일반화)가 아니니까 생략해도 되려나?
-> 이게 도대체 무슨 소리인가? 아는게 없으니 말도 이상하게 한다
?의문점 2
dfs(next)를 이용해서 다음 노드에서 dfs를 진행할 때 오름차순으로 진행중이라면 here보다 작은 숫자는 if문에서 제외하는 것이 더 낫지않나?
-> 안됨 말도안되는 소리! 연결된 노드들 중에서 오름차순인데 왜 here보다 작은거를 지우는거야 탐색을 안해버리면 안되지