1260번 - DFS와 BFS

문제

입출력

풀이

DFS - 깊이 우선 탐색

BFS - 너비 우선 탐색

#include <iostream>
#include <queue>
using namespace std;

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

void reset() {
    for (int i = 1; i <= N; i++) {
        visited[i] = 0; // DFS와 BFS 전에 모든 방문 여부를 0으로 초기화
    }
}

void DFS(int v) {
    visited[v] = true; // 첫 정점 방문 여부 체크
    cout << v << " "; // 첫 정점 출력
    for (int i = 1; i <= N; i++) {
        if (map[v][i] == 1 && visited[i] == 0) { // 현재 정점과 연결되어있고 방문되지 않았으면
            DFS(i); // 해당 정점으로 들어가 다시 탐색
        }
    }
}

void BFS() {
    while (!q.empty()) {
        int v = q.front(); // 첫 정점을 뽑아냄
        for (int i = 1; i <= N; i++) {
            if (map[v][i] == 1 && visited[i] == 0) { // 현재 정점과 연결되어있고 방문되지 않았으면
                q.push(i); // 해당하는 정점을 큐에 삽입
                visited[i] = true; // 해당하는 정점 방문 여부 체크
                cout << i << " "; // 출력
            }
        }
        q.pop(); // 탐색이 끝난 정점은 큐에서 팝
    }
}

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'; // DFS와 BFS를 줄 바꿈으로 구분 출력

    reset();
    q.push(V); // 첫 정점 등록
    visited[V] = true; // 첫 정점 방문 여부 체크
    cout << V << " "; // 첫 정점 출력
    BFS();

    return 0;
}