깊이 우선 탐색(DPS : Depth First Search)

코드

---

#include <iostream>
#include <vector>

using namespace std;

/* 그래프 => 총 노드의 수: 9 (0 포함)*/
bool visited[9]; // 방문 체크
vector<int> graph[9]; // 그래프

void dfs(int node)
{
    // 방문한 노드라면: 나가기
    if(visited[node]) return;

    // 방문표시, 출력
    visited[node] = true;
	printf("%d ", node);

    // 인접한 노드 탐색
	for (int i = 0; i < graph[node].size(); i++){
		int link = graph[node][i];
        
        dfs(link); 
	}
}

int main(void)
{
    /* 그래프 정의 */
    graph[0].push_back(1);

    graph[1].push_back(0);
    graph[1].push_back(2);
    graph[1].push_back(3);

    graph[2].push_back(1);
    graph[2].push_back(4);

    graph[3].push_back(1);
    graph[3].push_back(2);
    graph[3].push_back(4);
    graph[3].push_back(5);

    graph[4].push_back(2);
    graph[4].push_back(3);

    graph[5].push_back(3);
    graph[5].push_back(6);
    graph[5].push_back(7);

    graph[6].push_back(5);
    graph[6].push_back(8);

    graph[7].push_back(5);

    graph[8].push_back(6);

    dfs(0);
}

풀이

---

DFS(깊이 우선 탐색)

한우물을 파다가 끝이 보이면 지나왔던 길중 샛길로 빠지고 다시 그 곳을 판다 

 

dfs()설명: (방문 체크 -> 출력 -> 인접노드 탐색)

1. 방문한 노드인지 확인 (visited 이용) 

1-1. 방문한 노드라면 나가기

1-2. 방문 안한 노드라면 방문표시

2. 해당 노드를 출력 (출력뿐만 아니라 필요에 따라 다른 작업을 할 수도 있다)

3. 인접노드 탐색