[c/c++] 백준 1260 (Silver 2)

🔨 문제

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

<요약>
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하는 문제
여기서 조건이 있는데 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하는 것! 이것은 오름차순으로 방문하겠다는 것을 의미한다.

🔨 해결방법

문제를 잘 읽어야 하는데, 나는 앞서 알고리즘 수업을 4개를 풀어가지고 또 같은 문제구만 생각하고 풀었는데 예제가 하나도 안맞는겨..

보니까 각 노드의 방문 순서를 출력하는 것이 아니라 방문 순서에 따른 그 노드를 출력하는 거였다 히히😋

🔨 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

vector<vector<int>> graph;
vector<bool> visited;
queue<int> q;

void dfs(int cur) {
    visited[cur] = true;
    cout << cur << ' ';	// 방문하는 노드마다 해당 노드 출력
    for (int i = 0; i < graph[cur].size(); i++) {
        int next = graph[cur][i];
        if (!visited[next]) {
            dfs(next);
        }
    }
}

void bfs(int cur) {
    q.push(cur);
    visited[cur] = true;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        cout << cur << ' '; // 방문하는 노드마다 해당 노드 출력
        for (int i = 0; i < graph[cur].size(); i++) {
            int next = graph[cur][i];
            if (!visited[next]) {
                q.push(next);
                visited[next] = true;
            }
        }
    }
}

int main() {

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

    int n, line, start;
    cin >> n >> line >> start;

    graph.assign(n + 1, vector<int>(0, 0));
    visited.assign(n + 1, false);

    for (int i = 0; i < line; i++) {
        int n1, n2;
        cin >> n1 >> n2;
        graph[n1].push_back(n2);
        graph[n2].push_back(n1);
    }
    for (int i = 1; i <= n; i++) {
        sort(graph[i].begin(), graph[i].end());
    }

    dfs(start);
    cout << '\n';
    visited.assign(n + 1, false);	// 모든 노드들에 방문처리 취소
    bfs(start);

    return 0;
}