DFS와 BFS 1260

문제

접근 방법

DFS, BFS를 구현하여 사용하면 된다. 그래프 형식이기에 2차원 vector를 이용하여 만들어주고 sort를 해주면 된다.

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> graph;
int N, M, V;
vector<bool> isVisted;
void dfs(int cur)
{
    cout << cur << " ";
    for (int next : graph[cur])
    {
        if (isVisted[next])
            continue;
        isVisted[next] = true;
        dfs(next);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M >> V;
    graph = vector<vector<int>>(N + 1, vector<int>());
    isVisted = vector<bool>(N + 1);
    queue<int> bfs;
    for (int i = 0; i < M; ++i)
    {
        int p1, p2;
        cin >> p1 >> p2;
        graph[p1].push_back(p2);
        graph[p2].push_back(p1);
    }
    for (int i = 0; i <= N; ++i)
    {
        sort(graph[i].begin(), graph[i].end());
    }
    isVisted[V] = true;
    dfs(V);
    cout << "\n";
    fill(isVisted.begin(), isVisted.end(), false);
    isVisted[V] = true;
    bfs.push(V);
    while (!bfs.empty())
    {
        int cur = bfs.front();
        bfs.pop();
        cout << cur << " ";
        for (int next : graph[cur])
        {
            if (isVisted[next])
                continue;
            isVisted[next] = true;
            bfs.push(next);
        }
    }
    return 0;
}

풀이

정점의 범위는 1부터 N까지이므로 N+1 크기의 vector를 사용하거나 정점 입력을 받을 때 1 감소시켜서 받으면 된다.
반복문을 다시 쓰기 귀찮아서 입력에 사용한 것을 바꾸어 정렬에 사용하니 M만큼 돌아서 오류를 발생시켰었다.
그 후 N으로 수정했었는데 N 미만까지 돌았기에 오답으로 나왔다.
한번 실수를 고칠 때는 확실히 고치고 제출하는 게 맞는 거 같다.