60. C++ 백준 1260 번 DFS 와 BFS

안녕하세요. 코딩하는 덕구입니다. C++ 백준 1260 번 DFS와 BFS 입니다.

그래프 탐색 문제입니다.

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

1260번: DFS와 BFS

 

stack을 이용해 DFS를 구현했던 파이썬 버전과는 다르게

이번에는 재귀함수를 이용한 DFS를 C++을 통해 구현해보았습니다. 

 

먼저 방문할 노드 v를 입력받고

 방문표시를 해줍니다.

이후 해당 노드의 간선을 탐색하여, 다음 탐색할 노드를 물색하고,

만약 간선이 존재하고, 방문하지 않은 노드라면 DFS를 재귀적으로 호출해 해당 노드를 방문합니다.

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

 

 

다음은 큐를 이용한 BFS 입니다.

선입 선출의 특성을 가지는 큐를 이용하여 (FiFO) First In First Out

해당 큐에는 방문 가능한 후보 노드를 삽입하고

노드를 꺼내면서, 방문하지 않았으면 방문하는 방식의 코드입니다.

 

먼저 시작 정점인 v를 입력받아 큐에 넣습니다.

1.  해당 노드는 방문처리 해주고,

2. v와 연결된 간선을 살피며, 방문하지 않았다면,  queue에 넣습니다.

방문 가능한 후보 노드가 없을 때 까지 1, 2를 반복합니다.

 

void BFS(int v) {
    q.push(v);
    visited[v] = true;
    cout << v << " ";
    while (!q.empty()) {
        v = q.front();
        q.pop();
        for (int w = 1; w <= N; w++) {
            if (map[v][w] == 1 && visited[w] == 0) { //현재 정점과 연결되어있고 방문되지 않았으면
                q.push(w);
                visited[w] = true;
                cout << w << " ";
            }
        }
    }
}

 

백준 1260 번 C++  최종 코드입니다.

#include <iostream>
#include <queue>
using namespace std;
#define MAX 1001

int N, M, V; //정점개수, 간선개수, 시작정점
int map[MAX][MAX]; //인접 행렬 그래프
bool visited[MAX]; //정점 방문 여부
queue<int> q;

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

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

void BFS(int v) {
    q.push(v);
    visited[v] = true;
    cout << v << " ";
    while (!q.empty()) {
        v = q.front();
        q.pop();
        for (int w = 1; w <= N; w++) {
            if (map[v][w] == 1 && visited[w] == 0) { //현재 정점과 연결되어있고 방문되지 않았으면
                q.push(w);
                visited[w] = true;
                cout << w << " ";
            }
        }
    }
}

int main() {
    cin >> N >> M >> V;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        map[a][b] = 1;
        map[b][a] = 1;
    }
    reset();
    DFS(V);
    cout << '\n';
    reset();
    BFS(V);
    return 0;
}

 

감사합니다.