백준 - 1260 ( C++ ) DFS 와 BFS

 

안녕하세요 besforyou입니다.

 

백준 문제 1260 소개를 시작하겠습니다.

 

---

문제 풀이

 

입력받은 정점과 간선들로 그래프를 생성하고 DFS search, BFS search를 해주면 된다.

 

DFS 탐색 방법 : https://besforyou.tistory.com/122

Depth First Search for a Graph - 그래프 깊이-우선 탐색

BFS 탐색 방법 : https://besforyou.tistory.com/121

Breadth First Search for a Graph - 그래프 넓이-우선탐색

 

---

코드

필요한 변수들을 전역 변수로 선언합니다.

 

const int MAX = 1001;
int N, M, V;
int visited[MAX];
int mat[MAX][MAX];
queue<int> q;

 

우선 주어지는 데이터를 입력받아 그래프를 생성합니다. 정점 사이에 간선이 몇 개 있는지는 알 필요가 없으므로 정점 사이에 간선이 존재하는 것만 나타내 줍니다.

 

그다음 DFS, BFS를 해주면 됩니다.

int main (void) {
   
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int first, second;
    cin >> N >> M >> V;

    for ( int i = 0 ; i < M ; i++ ) {
        cin >> first >> second;
        mat[first][second] = 1;
        mat[second][first] = 1;
    }

    DFS(V);
    reset();
    BFS(V);

    return 0;
}​

 

DFS

void DFS(int v) {
    visited[v] = 1;
    cout << v << " ";
    for ( int i = 1 ; i <= N ; ++i ) {
        if ( mat[v][i] == 1 && visited[i] == 0 )
            DFS(i);
    }
}​

 

깊이-우선 탐색 코드는 간단합니다. 방문한 정점을 기록하고 반복문안에서 현재 정점과 이어져 있고 아직 방문하지 않은 정점이 있다면 그 정점을 인자로 주어 DFS 함수를 재귀적으로 호출합니다.

 

BFS

 

void BFS( int s ) {

    q.push(s);
    visited[s] = 1;

    while (!q.empty()) {
        s = q.front();
        cout << s << " ";
        q.pop();
        for ( int i = 1 ; i <= N ; ++i) {
            if ( mat[s][i] == 1 && visited[i] == 0 ) {
                q.push(i);
                visited[i] = 1;
            }
        }
    }
}

 

넓이-우선 탐색입니다.

현재 보고 있는 정점을 전역으로 선언한 큐에 push 하고 방문했다는 기록을 합니다.

 

큐가 빌 때까지 반복문안에서

큐 가장 앞 원소를 출력하고 큐에서 제거합니다.

이후에 for문안에서 현재 보고 있는 정점과 이어져있고 방문하지 않은 정점이 있다면 해당 정점을 큐에 push 하고 방문하였다는 기록을 합니다.

 

Reset 함수

void reset() {
    for ( int i = 1; i <= N ; i++ ) {
        visited[i] = 0;
    }
    cout << endl;
}​

 

전역으로 선언한 배열 visited를 0으로 초기화하는 함수입니다.

 

---

전체 코드

#include <iostream>
//#include <list>
#include <queue>

using namespace std;

const int MAX = 1001;
int N, M, V;
int visited[MAX];
int mat[MAX][MAX];
queue<int> q;

void BFS( int s ) {

    q.push(s);
    visited[s] = 1;

    while (!q.empty()) {
        s = q.front();
        cout << s << " ";
        q.pop();
        for ( int i = 1 ; i <= N ; ++i) {
            if ( mat[s][i] == 1 && visited[i] == 0 ) {
                q.push(i);
                visited[i] = 1;
            }
        }
    }
}

void DFS(int v) {
    visited[v] = 1;
    cout << v << " ";
    for ( int i = 1 ; i <= N ; ++i ) {
        if ( mat[v][i] == 1 && visited[i] == 0 )
            DFS(i);
    }
}

void reset() {
    for ( int i = 1; i <= N ; i++ ) {
        visited[i] = 0;
    }
    cout << endl;
}

int main (void) {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int first, second;
    cin >> N >> M >> V;

    for ( int i = 0 ; i < M ; i++ ) {
        cin >> first >> second;
        mat[first][second] = 1;
        mat[second][first] = 1;
    }

    DFS(V);
    reset();
    BFS(V);

    return 0;
}

결과