[백준 1260번] DFS와 BFS

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

DFS와 BFS 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	37893	11688	7042	29.386%

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 한 간선이 여러 번 주어질 수도 있는데, 간선이 하나만 있는 것으로 생각하면 된다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1 

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1 

1 2 4 3
1 2 3 4

시험공부하다가 머리 식힐겸 잠깐 풀어봤는데 생각보다 오류가 많이 생겨서 불편했던 문제이다.

시간초과가 발생해서 최대한 메모리 접근을 줄였더니 성공했다.

#include<iostream>
#include<queue>
#include<memory.h>
 
using namespace std;
 
void dfs(int);
void bfs();
 
int N, M, start, a, b, flag;
bool check[1001][1001], visited[1001];
queue<int> q;
 
int main() {
 
    std::ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> N >> M >> start;
 
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        check[a][b] = true;
        check[b][a] = true;
    }
 
    cout << start << " ";
 
    visited[start] = true;
    flag = 1;
    dfs(start);
 
    cout << "\n";
 
    memset(visited, false, sizeof(bool) * 1001);
    visited[start] = true;
    q.push(start);
    bfs();
 
    return 0;
}
 
void dfs(int point) {
 
    if (flag == N) {
        return;
    }
        
    for (int i = 1; i <= N; i++) {
        if (flag == N) return;        
        if (check[point][i] == true && visited[i] == false) {
            cout << i << " ";
            flag++;
            visited[i] = true;
            dfs(i);
        }
    }
 
}
 
void bfs() {
 
    int a;
 
    while (!q.empty()) {
 
        a = q.front();
        q.pop();
        cout << a << " ";
 
        for (int i = 1; i <= N; i++) {
            if (check[a][i] == true && visited[i] == false) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
 
}