[백준 c++] 1260번: DFS와 BFS

문제 링크입니다

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

1260번: DFS와 BFS

 

DFS, BFS에 대한 설명은 아래 링크를 참고해주세요.

https://dvpzeekke.tistory.com/37?category=887119

[c++] DFS(Depth First Search) 알고리즘

https://dvpzeekke.tistory.com/36?category=887119

[c++] BFS(Breadth First Search) 알고리즘

 

 

//
//  main.cpp
//  1260
//
//  Created by Jihye on 2020/01/14.
//  Copyright © 2020 Jihye Han. All rights reserved.
//

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int MAX = 1000 + 1;

int N, M, V;
int map[MAX][MAX];
bool visited[MAX];
queue<int> q;

void DFS(int index) {
    visited[index] = true;
    cout << index << " ";
    
    for (int i = 1; i <= N; i++) {
        if ((!visited[i]) && (map[i][index] == 1)) {
            DFS(i);
        }
    }
}

void BFS(int index) {
    q.push(index);
    visited[index] = true;
    
    while (!q.empty()) {
        index = q.front();
        q.pop();
        cout << index << " ";
        
        for (int i = 1; i <= N; i++) {
            if ((!visited[i]) && (map[index][i] == 1)) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
    
}

int main(void) {
    
    cin >> N >> M >> V;
    
    for (int i = 0; i < M; i++) {
        int from, to;
        
        cin >> from >> to;
        map[from][to] = 1;
        map[to][from] = 1;
    }
    
    DFS(V);
    cout << endl;
    
    memset(visited, false, sizeof(visited));
    BFS(V);
    cout << endl;
    
    return 0;
}