BOJ 1260번 : DFS와 BFS

다른 문제를 풀다가 DFS구현에서 계속 문제가 발생해서 초심으로 돌아가고자 DFS와 BFS를 복습...할겸 풀었다. 

역시나 자주 사용하지 않던 알고리즘이라 그런지 구현 방식부터 틀렸었더라..... 공부하자 공부!

 

<개념>

위 그림을 바탕으로 DFS, BFS 의 개념을 보자.

 

DFS (Depth First Search)는 깊이 우선 탐색 이다.

가장 깊은 노드 를 우선으로 탐색하는 방식으로, 탐색 순서는 아래와 같다.

BFS (Breadth First Search)는 넓이 우선 탐색 이다.

깊은곳이 아니라 같은 계층에 있는 노드을 먼저 탐색하는 방식으로, 탐색 순서는 아래와 같다.

탐색 주체로부터 가장 가까운 노드부터 방문하게 되므로 "최소" 비용, "최단" 거리등의 문제는 bfs를 사용할 확률이 높다.

이제 각 알고리즘의 구현을 보자.

 

DFS는 스택을 사용하거나, 재귀를 사용한다.

사실상 재귀로 구현하게 되면, 시스템 스택을 사용하는 것과 마찬가지이다.

또한, 재귀로 구현되기에 구현도가 쉽다. 코드는 아래와 같다.

void DFS(int v) {
    dhis[v] = 1;                // 방문표시
    cout << v << ' ';
    for (int i = 1; i <= n; i++) {
        if (arr[v][i] && !dhis[i])  // 방문하지 않았고, 연결된 노드라면?
            DFS(i);                 // 탐색
    }
}

가장 중요한 것은 탐색할 노드가 이미 방문을 했는지 확인을 해야 한다는 것이다. 그러기때문에 check 하는 배열을 따로 만들어, 방문한 노드 인덱스 의 값을 1로 만들어 주어야 한다.

 

BFS는 큐를 사용한다.

자신과 같은 계층에 있는 노드를 모두 큐에 저장하고, 큐에서 front에 있는 노드를 순차적으로 탐색한다.

그림으로 보자면 아래와 같다.

이 또한 방문한 노드를 체크하는것은 필수 이다.

코드는 아래와 같다.

void BFS(int v) {
    bhis[v] = 1;
    q.push(v);
    while (!q.empty()) { // 큐 빌때까지 반복
        v = q.front(); //아래에서 큐에 넣은것 빼서 확인하기
        q.pop();
        cout << v << ' ';
        for (int i = 1; i <= n; i++) { //한줄 탐색
            if (arr[v][i] && !bhis[i]) { //연결 되어있고, 방문하지 않은 노드들
                bhis[i] = 1; // 방문 표시 하고
                q.push(i);  // 큐에 집어 넣음
            }
        }
    }
}

 

<Solution>

문제에서 각 노드의 번호로 연결을 표시하기에 2차원 배열로 받고, 노드에 대한 정보를 구현할 수 있다.

 

<소스코드>

#include<iostream>
#include<queue>
using namespace std;
 
int n, m, v;
int arr[1001][1001] = { 0, };
int dhis[1001] = { 0, }; //DFS 방문표시 배열
int bhis[1001] = { 0, }; //BFS 방문표시 배열
queue<int> q;
 
void DFS(int v) {
    dhis[v] = 1;                // 방문표시
    cout << v << ' ';
    for (int i = 1; i <= n; i++) {
        if (arr[v][i] && !dhis[i])  // 방문하지 않았고, 연결된 노드라면?
            DFS(i);                 // 탐색
    }
}
 
void BFS(int v) {
    bhis[v] = 1;
    q.push(v);
    while (!q.empty()) { // 큐 빌때까지 반복
        v = q.front(); //아래에서 큐에 넣은것 빼서 확인하기
        q.pop();
        cout << v << ' ';
        for (int i = 1; i <= n; i++) { //한줄 탐색
            if (arr[v][i] && !bhis[i]) { //연결 되어있고, 방문하지 않은 노드들
                bhis[i] = 1; // 방문 표시 하고
                q.push(i); // 큐에 집어 넣음
            }
        }
    }
}
 
 
void Solve() {
    cin >> n >> m >> v;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        arr[x][y] = arr[y][x] = 1;
    }
    DFS(v);
    cout << endl;
    BFS(v);
 
}
 
int main() {
    Solve();
}

<문제>

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS