[BOJ] 1260 DFS와 BFS

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;
vector<vector<int> > v;
int visit[1001];

void dfs(int idx)
{
    visit[idx] = 1;
    printf("%d ", idx);

    sort(v[idx].begin(), v[idx].end());
    for (int i = 0; i < v[idx].size(); i++) {
        if (visit[v[idx][i]] == 0)
            dfs(v[idx][i]);
    }
}

int main()
{
    int n, m, start;
    queue<int> q;

    scanf("%d %d %d", &n, &m, &start);
    v.resize(n + 1);

    int x, y;
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(start);
    printf("\n");

    memset(visit, 0, sizeof(visit));
    q.push(start);
    while (!q.empty()) {
        if (visit[q.front()] == 1) {
            q.pop();
            continue;
        }
        visit[q.front()] = 1;
        for (int i = 0; i < v[q.front()].size(); i++) {
            if (visit[v[q.front()][i]] == 0)
                q.push(v[q.front()][i]);
        }
        printf("%d ", q.front());
        q.pop();
    }

    return 0;
}

풀이 및 코딩: 23분

while문 시작에 visit 여부를 확인하지 않아도 될 줄 알았는데 queue에 들어있지만 아직 출력되지 않은 노드가 중복으로 push되는 일이 있어서 코드를 추가했다.
4 5 1
1 2
1 3
1 4
2 4
3 4
위 입력이라면 아래와 같이 중복이 발생한다.
1 2 4 3
1 2 3 4 4 4
중복 없는 queue는 왜 없나 싶었는데 중복 여부를 판단하는 오래 걸려서 없는 것 같다.
입력이 n개면 중복을 탐지해서 넣는데 총 O(n^2) 시간이 필요하다. 꼭 필요하면 만들어서 쓸 수 있겠지만.