글 읽기 - DFS 시간초과 원인을 잘 모르겠습니다.

qkrcksgur38 1년 전 0

현재 시간초과가 나오는 상태입니다.

입력 / 정렬 부분이 아닌 dfs 구현 과정에서 시간초과가 났다고 생각하는데

혹시 시간을 줄일 수 있는 방법 알려주시면 감사하겠습니다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
using namespace std;

bool visited_dfs[100001];
int ans[100001] = {0};
int cnt = 2;

void dfs(vector<int>* graph, int current) {
    visited_dfs[current] = true;
    for (int next : graph[current]) {
        if (!visited_dfs[next]) {
            ans[next] = cnt++;
            dfs(graph, next);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int n, m, v;
    cin>>n>>m>>v;
    
    vector<int> g[100001];

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    
    for (int i = 0; i < n; i++) {
        sort(g[i].begin(), g[i].end());
    }

    ans[v] = 1;
    dfs(g, v);
    
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << endl;
    }
    
    return 0;
}

dh0450 1년 전 0

문제는 endl 입니다.

endl 은 커서를 다음줄로 옮김과 동시에 버퍼를 비우는데 이 과정을 반복하면 시간이 굉장이 오래결리게 됩니다.

그래서 많은양을 출력할 때는 대신 '\n' 같은 줄바꿈 문자를 사용하여야 합니다.

qkrcksgur38 1년 전 0

감사합니다. 덕분에 PS할때는 개행문자 사용하는 습관 들이게 되었습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

DFS 시간초과 원인을 잘 모르겠습니다.

qkrcksgur38 1년 전 0

dh0450 1년 전 0

qkrcksgur38 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말