DFS

DFS

그래프를 탐색할 때 쓰는 알고리즘이며 어떤 노드부터 시작해 인접한 노드들을 재귀적으로 방문하며 방문한 정점은 다시 방문하지 않으며 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘

 

DFS(u, adj){
	u.visited = true;
    for (each = adj[u]){
    	if (v, visited == 0)
        	DFS(u, adj)
    }
}

 

#include <iostream>
#include <vector>

using namespace std;

const int v = 10;
vector<int> adj[v];
int visited[v];

void dfs(int u){
    visited[u] = true;
    cout << u << '\n';
    for (int v : adj[u]){
        if (visited[v] == 0){
            dfs(v);
        }
    }
    cout << u << " 로 부터 함수 종료" << '\n';
}

int main()
{
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(4);
    adj[4].push_back(2);
    adj[2].push_back(5);
    dfs(1);
}

 

 

1. 구현 방법 : 돌다리를 두들겨 보기

void dfs(int here){
	visited[here] = 1;
    for (int there : adj[here]){
    	if (visited[there]) continue;
        dfs(there);
    }
}

 

2. 못 먹어도 GO

void dfs(int here){
	if (visited[here]) return;
    visited[here] = 1;
    for (int there : adj[here]){
    	dfs(there);
    }
}

 

 

ex) 

#include <iostream>

using namespace std;

int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int m, n, k, y, x, ret, ny, nx, t;
int a[104][104];
bool visited[104][104];

void dfs(int y, int x){
    visited[y][x] = 1;
    // 4방향
    for (int i = 0; i < 4; i++){
        ny = y + dy[i];
        nx = x + dx[i];
        if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
        if (a[ny][nx] == 1 && !visited [ny][nx]){
            dfs(ny, nx);
        }
    }
}

int main()
{
    cin >> n >> m;
    // 입력 받는 부분
    for (int i = 0 ; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            if (a[i][j] == 1 && !visited[i][j]){
                ret++;
                dfs(i, j);
            }
        }
    }
    cout << ret << '\n';
}


/*
 5 5
 1 0 1 0 1
 1 1 0 0 1
 0 0 0 1 1
 0 0 0 1 1
 0 1 0 0 0
 
 4
 */