[백준 1260번] DFS와 BFS

[백준 1260번] DFS와 BFS 소스 코드입니다.

[백준 1260번 URL]

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

DFS와 BFS의 기본 개념을 알고 싶으신 분은 클릭해주세요.

2019/02/11 - [알고리즘 이론] - BFS와 DFS의 기초 개념 -1

1. 각 노드간의 연결 상태는 vector에 저장한다.

예를 들어, 0번 노드와 연결된 경우 graph[0]에 차곡차곡 저장한다.

즉, 0번 노드와 연결된 노드의 갯수는 graph[0].size()이다.

2. 각 노드간의 연결상태를 저장했다면 visited 배열을 통해 차근차근 방문한다.

반복문을 통해 graph[0]부터 차근차근 접근한다.

예시)

graph[0] 에 저장된 값이 1, 2, 3이라면 0번 노드와 1, 2, 3번 노드는 연결된 상태이므로

visited[1], visited[2], visited[3] 을 true로 바꿔준다.

visited 값이 true이면 해당 노드를 방문했다는 뜻이다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
#define MAX 1001
 
vector<int> graph[MAX];
bool visited[MAX];
int n, m, v;
 
void dfs(int v) {
 
    cout << v << " ";
    visited[v] = true;
 
    for (int i = 0; i < graph[v].size(); i++) {
        int x = graph[v][i];
        if (!visited[x]) {
            dfs(x);
        }
    }
 
}
 
void bfs(int v) {
 
    queue<int> q;
    q.push(v);
    visited[v] = true;
 
    while (!q.empty()) {
 
        int x = q.front();
        q.pop();
        cout << x << " ";
 
        for (int i = 0; i < graph[x].size(); i++) {
            int y = graph[x][i];
            if (!visited[y]) {
                visited[y] = true;
                q.push(y);
            }
        }
 
    }
 
}
 
int main(void) {
 
    cin >> n >> m >> v;
    for (int i = 0; i < m; i++) {
        int num1, num2;
        cin >> num1 >> num2;
        graph[num1].push_back(num2);
        graph[num2].push_back(num1);
    }
 
    for (int i = 1; i <= n; i++) {
        sort(graph[i].begin(), graph[i].end());
    }
 
    dfs(v);
    memset(visited, false, sizeof(visited));
    cout << endl;
    bfs(v);
 
    return 0;
}