알고리즘 정리 - DFS, BFS

DFS(깊이 우선 탐색)

 

DFS는 파고들 수 있을 만큼 계속 파고들다가 더 파고들곳이 없을때까지 탐색을 진행하고, 그 후 이전으로 되돌아가 다시 탐색을 시작.

 

1. 첫번쨰 노드를 방문처리.

2. 노드에 대한 작업을 진행.

3. 현재 노드와 연결되어 있으면서 방문하지 않은 노드를 dfs로 검사.(재귀적)

4. 2,3을 모든 노드를 탐색할 때까지 반복.

 

#include <bits/stdc++.h>

using namespace std;

bool visited[9]; //노드의 방문 여부. 
vector<int> graph[9];

// DFS 함수 정의
void dfs(int x) {
    // 현재 노드를 방문 처리
    visited[x] = true;
    cout << x << ' ';
    // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for (int i = 0; i < graph[x].size(); i++) {
        int y = graph[x][i];
        if (!visited[y]) dfs(y);
    }

 

여기서 핵심은 현재 노드를 "방문처리" 하고, 연결된 다음 노드를 재귀적으로 방문해나간다는 것이다.

 

#include <bits/stdc++.h>

using namespace std;

int n, m;
int graph[1000][1000];

// DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
bool dfs(int x, int y) {
    // 주어진 범위를 벗어나는 경우에는 즉시 종료
    if (x <= -1 || x >=n || y <= -1 || y >= m) {
        return false;
    }
    // 현재 노드를 아직 방문하지 않았다면
    if (graph[x][y] == 0) {
        // 해당 노드 방문 처리
        graph[x][y] = 1;
        // 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
        dfs(x - 1, y);
        dfs(x, y - 1);
        dfs(x + 1, y);
        dfs(x, y + 1);
        return true;
    }
    return false;
}

int main() {
    // N, M을 공백을 기준으로 구분하여 입력 받기
    cin >> n >> m;
    // 2차원 리스트의 맵 정보 입력 받기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &graph[i][j]);
        }
    }
    // 모든 노드(위치)에 대하여 음료수 채우기
    int result = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 현재 위치에서 DFS 수행
            if (dfs(i, j)) {
                result += 1;
            }
        }
    }
    cout << result << '\n'; // 정답 출력 
}

 

해당 dfs 함수에서 방문을 확인하는 visted는 없지만 실제 그래프에 방문처리를 1로 표시하는 것을 확인할 수 있다.

 

BFS(깊이 우선 탐색)

BFS는 현재 단계의 노드들을 모두 탐색한 후 다음 레벨로 탐색을 진행하는 방식이다.

 

1. 첫번쨰 노드를 방문처리하고 큐에 넣는다.

2. 큐에서 pop하고, 현재 노드에 대한 작업을 진행.

3. 현재 노드와 연결되어 있는 노드를 모두 큐에 넣는다.

4. 2,3을 큐가 빌때까지 반복.

 

#include <bits/stdc++.h>

using namespace std;

bool visited[9];
vector<int> graph[9];

// BFS 함수 정의
void bfs(int start) {
    queue<int> q;
    q.push(start);
    // 현재 노드를 방문 처리
    visited[start] = true;
    // 큐가 빌 때까지 반복
    while(!q.empty()) {
    	// 큐에서 하나의 원소를 뽑아 출력
        int x = q.front();
        q.pop();
        cout << x << ' ';
        // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for(int i = 0; i < graph[x].size(); i++) {
            int y = graph[x][i];
            if(!visited[y]) {
                q.push(y);
                visited[y] = true;
            }
        }
    }
}