DFS(깊이 우선 탐색)

깊이 우선 탐색

(depth-first search: DFS)

 

 정의 

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를

완벽하게 탐색하는 방법

미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사

 

 알고리즘 

 

1. 시작지점을 기준으로 이동가능한 경우 자기자신을 호출(재귀 함수) 를 통하여 방문가능한 곳까지 방문.

2. 이미 방문하였거나 더이상 방문할 수 없을경우 return.

 

 코드 

 

 
//그래프의 컴포넌트 갯수구하기
int dfsAll() {
 
    int cnt = 0;
 
    for (int i = 0; i < 100; i++) {
 
        for (int j = 0; j < 100; j++) {
 
            if (!visited[i][j]) {
                dfs(i, j);
                cnt++;
            }
 
        }
    }
 
    //컴포넌트 갯수
    return cnt;
}
void dfs(int x, int y) {
 
    //이미방문하였다면 return
    if (visited[x][y]) return;
 
    //방문 체크
    visited[x][y] = 1;
 
    //상,하,좌,우 4방향 탐색
    for (int i = 0; i < 4; i++) {
 
        int next_x = x + dx[i];
        int next_y = y + dy[i];
 
        if (next_x >= 0 && next_x < 100 && next_y >= 0 && next_y < 100) {
 
            //탐색가능하다면 재귀호출.
            if (map[next_x][next_y] && !visited[next_x][next_y])
                dfs(next_x, next_y);
        }
    }
}