[C++] 백준 BOJ 1260 DFS와 BFS

문제링크 : https://boj.kr/1260

가장 기본적인 DFS, BFS 문제이다.

시간초과 때문에 애먹었었는데.. 백준 사이트 자체 채점 시스템은 제약조건이 너무 많은 것 같다.

std::cin과 같은 것도 조심해야 하고 for each 구문도 조심해야 하는듯....

편하려고 STL을 사용하면 문제 생기는 부분이 좀 있는 것 같다.

void dfs(int num){
    if(!visited[num])
        sort(node[num].begin(), node[num].end());
    visited[num] = true;
    for(int i : node[num]) {
        if (!visited[i]) {
            cout << i << " ";
            dfs(i);
        }
    }
}

처음에 이런 식으로 for(int i : node[num]) 로 작성했더니 시간초과가 나왔다.

sort의 문제인가 다른 최적화의 문제인가 고민하다가 일반 문장으로 바꾸니 해결되었다.

// BOJ 1260 DFS와 BFS
#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> node[1001]; // 그래프
bool visited[1001];     // 방문 체크
queue<int> qq;         // BFS용 큐
 
void dfs(int num){
    if(!visited[num])
        sort(node[num].begin(), node[num].end());
    visited[num] = true;
    for(int i = 0; i < node[num].size(); i++) {
        int a = node[num][i];
        if (!visited[a]) {
            cout << a << " ";
            dfs(a);
        }
    }
}
 
void bfs(int num){
    qq.push(num); visited[num] = true; // 첫항
    while(!qq.empty()){
        int nn = qq.front();
        qq.pop(); // poll
        if(!visited[nn])
            sort(node[nn].begin(), node[nn].end());
        for(int i = 0; i < node[nn].size(); i++){
            int a = node[nn][i];
            if(!visited[a]) {
                visited[a] = true;
                cout << a << " ";
                qq.push(a);
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("../input.txt", "r", stdin);
 
    // 입력
    int num, edg, ptr;
    cin >> num >> edg >> ptr;
    int a, b;
    for(int i = 0; i < edg; i++){
        cin >> a >> b;
        // 양방향 그래프 만들기
        node[a].push_back(b);
        node[b].push_back(a);
    }
 
    memset(visited, false, sizeof(visited));
    cout << ptr << " ";
    dfs(ptr);
    cout << "\n";
 
    memset(visited, false, sizeof(visited));
    cout << ptr << " ";
    bfs(ptr);
 
    return 0;
}