깊이우선탐색(DFS) vs 너비우선탐색(BFS)

탐색이란, 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘이다.

즉, 주어진 데이터 성질(정렬 데이터 또는 비정렬 데이터)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요하다.

 

 

https://blog.naver.com/jhc9639/222289089015

[알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회

 

그래프를 탐색할 때 쓰는 알고리즘들

---

깊이우선탐색(DFS, Depth First Search)

 

어떤 노드부터 시작해 인접한 노드들을 재귀적으로 방문

방문한 정점은 다시 방문하지 않으며,

각 분기(가지)마다 가능한 가장 멀리 있는 노드까지 탐색

 

PSEUDO CODE

*수도 코드(pseudocode) : 프로그램 로직을 표현하기 위해 쓰는 코드

DFS(u, adj)		//u :from 정점, adj : 인접리스트
	u.visited = true;	//  인접한 정점 하나씩 방문!
    for each v ∈ adj[u]
    	if v.visited == false	// 방문하지 않았다면 방문
        	DFS(v,adj)

 

CODE

#include <bits/stdc++.h>
using namespace std;

const int n = 6;
vector<int> adj[n];
int visited[n];

void dfs(int u){
    visited[u] = 1;
    cout << u << "\n";

    for (int v : adj[u]){
        if(visited[v] == 0){
            dfs(v);
        }
    }

    cout << u << "로부터 시작된 함수가 종료되었습니다\n";
    return;
}

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);
}

재귀함수가 뻗어나가는 과정을 시각화하기가 힘들었는데 "로부터 시작된 함수가 종료되었습니다"디버깅 팁

 

DFS 구현 방법 (2)

• 1. 방문했는지 체크 후 이동

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

• 2.  방문했든 안했든 이동 , 무조건 일단 함수 호출

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

 

둘 다 자유롭게 구현할 줄 알아야 한다.

---

DFS 예제

Q. 방귀를 뀌면 상하좌우 네 방향으로 종화와 연결된 육지는 모두 오염된다.

바다는 오염되지 않는다. 방귀를 몇번 뀌어야 모든 육지를 오염시킬 수 있는지

 

입력

맵의 세로길이 N과 가로길이 M이 주어지고 이어서 N*M의 맵이 주어진다.

 

출력

1 <= N <=100, 1 <=M <=100

 

#include <bits/stdc++.h>
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];

//2차원
void dfs(int y, int x){
    visited[y][x] = 1;

    cout << y << " : " << x << '\n';

    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);
        }
    }
    return;
}

int main(){
    cin.tie(NULL); cout.tie(NULL);

    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]){

                cout << i << " : "
                     << " dfs가 시작됩니다.\n";
                dfs(i, j);
                ret++; 
                
            }
        }
    }
    cout << ret << '\n';
    return 0;
}

---

너비우선탐색(BFS, Breath First Search)

 

그래프를 탐색하는 알고리즘

어떤 정점에서 시작해 다음 깊이의 정점으로 이동하기 전 현재 깊이의 모든 정점을 탐색

방문한 정점은 다시 방문하지 않음.

같은 가중치를 가진 그래프에서 최단거리 알고리즘으로 쓰인다.

 

레이어별,레벨별로 탐색한다.

 

 

 

Queue 선입선출 특성 활용하여 구현

 

 

PSEUDO CODE

*수도 코드(pseudocode) : 프로그램 로직을 표현하기 위해 쓰는 코드

queue<int> q;
q.push(here);
visited[here] = 1;

while(q.size()){
	int here = q.front();
    q.pop();
    
    for(int there: adj[here]{
    	if(visited[there]) continue;
    	visited[there] = visited[here] + 1;
    	q.push(there);
    }
}

BFS(G, u)
	u.visited = 1;		//방문을 체크해야 함.
    q.push(u);
    
    while(q.size())
    	u = q.front()
        q.pop()
        for each v ∈ G.Adj[u]
        	if v.visited == false
            	v.visited == u.visited + 1	//방문배열이자 최단거리 담는 배열으로도 쓰인다.
                q.push(v)

 

CODE

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[100];
int visited[100];
int nodeList[] = {10,12,14,16,18,20,22,24};

void bfs(int here){
    queue<int> q;
    visited[here] = 1;
    q.push(here);

    while(q.size()){
        int here = q.front(); q.pop();

        for(int there : adj[here]){
            if(visited[there]) continue;
            visited[there] = visited[here]+1;
            q.push(there);
        }
    }
}

int main(){
    adj[10].push_back(12);
    adj[10].push_back(14);
    adj[10].push_back(16);

    adj[12].push_back(18);
    adj[12].push_back(20);

    adj[20].push_back(22);
    adj[20].push_back(24);

    bfs(10);

    for(int i : nodeList){
        cout << i << " :  " << visited[i] << '\n';
    }

    cout << "10번으로부터 24번까지 최단거리는 : " << visited[24] - 1<<'\n';
    return 0;

}

 

Q. BFS는 왜 가중치가 같은 그래프내에서만 최단거리 알고리즘으로 쓰이나요? 가중치가 다른 그래프에서는 안되나요?

visited[there] =  visited[here] + 1로 가중치를 1씩 더해주고 있기 때문에!

 

참고로 가중치가 다른 그래프 내에서 최단거리 알고리즘은 다익스트라, 벨만포드 등을 써야 한다.

---

BFS 구현 방법(2)

• 방문 처리만 하는 코드 : 시작지점 u를 방문처리 하고 queue에 Push

BFS(G,u)
	u.vitied = true
    q.push(u);
    while(q.size())
    	u = q.front()
        q.pop()
        
        for each v ∈ G.Adj[u]
        	if v.visited == false
            	v.visited = true
                q.push(v)

 

• 최단거리 배열까지 만드는 코드

BFS(G,u)
	u.visited = 1
    q.push(u);
    while(q.size())
    	u = q.front()
        q.pop()
        for each v ∈ G.Adj[u]
        	if v.visited == false
            	v.visited = u.visited +1
                q.push(v)

---

예제

한 칸 움직일 때마다 당근 하나가 소모된다. 최단거리로 당근마켓으로 향할 때 몇 개를 소모해야 당근 마켓에 갈 수 있는지.

#include <bits/stdc++.h>
using namespace std;

const int max_n = 104;
int dy[] = {-1,0,1,0};
int dx[] = {0,1,0,-1};

int n, m, a[max_n][max_n], visited[max_n][max_n], y,x,sy,sx,ey,ex;

int main(){
    scanf("%d %d", &n,&m);
    cin >> sy >> sx;
    cin >> ey >> ex;

    for(int i = 0; i <n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }

    queue<pair<int, int>> q;

    visited[sy][sx] = 1;
    q.push({sy,sx});

    while(q.size()){
        tie(y,x) = q.front(); q.pop();  //여러 변수를 묶어서 하나의 변수로 사용

        for(int i = 0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(ny <0 || ny >=n || nx < 0 || nx>=m || a[ny][nx]== 0) continue;

            if(visited[ny][nx]) continue;

            visited[ny][nx] = visited[y][x] +1;
            q.push({ny,nx});
        }
    }
}

---

DFS와 BFS 비교

퍼져나간다. 탐색한다 2글자가 있으면 반드시 DFS, BFS 떠올려야 한다.

DFS(Depth First Search)	BFS(Breath First Search)
시간복잡도는 인접리스트로 이루어졌다면 O(V+E) 이고, 인접행렬로 이루어졌다면 O(V^2)로 동일
메모리를 덜 씀	메모리를 더 씀
절단점 등을 구할 수 있음	가중치가 같은 그래프 내에서 최단거리를 구할 수 있음
코드가 좀 더 짧으며 완전탐색의 경우 많이 씀	코드가 더 김