백준 1260 - DFS와BFS - DFS

문제

문제링크 : https://www.acmicpc.net/problem/1260

풀이전략

1. 시간은 2초로 충분하므로 우리가 아는 DFS, BFS를 하면 된다. DFS는 재귀로, BFS는 queue로 구현하였다.
2. 또한 output을 보면 인풋 3 4 와 3 1의 순서는 3 1이 더 느리지만 출력은 3다음에 1이 먼저 나왔다. 따라서 이는 serch할 때 더 작은 숫자를 우선적으로 탐색한다는 것을 알 수 있다.
   1

코드

#include<bits/stdc++.h>
#include<queue>
using namespace std;

int N, M, V;
int a[1002][1002] = {0, };
bool ch[1002] = {false, };

void DFS(int v){
    
    for(int i=1; i<=N; i++){
        if(ch[i] == false && a[v][i] == 1){
            ch[i] = true;
            cout<<i<<" ";
            DFS(i);
        }
    }
    return;
}

void BFS(int v){
    queue<int> q;
    q.push(v);

    while(!q.empty()){
		// 여기서 while문에 q.empty()부분을 꼭 넣어주어야 한다. 
        while((ch[q.front()] != false) && !q.empty()) q.pop();
        if(q.empty()) break;
        int ft = q.front();
        ch[ft] = true;
        cout<<ft<<" ";
        q.pop();
        for(int i=1; i<=N; i++){
            if(ch[i]==false && a[ft][i] == 1){
                // ch[i] = true;
                q.push(i);
            }
        }
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N >> M >> V;
    int ta, tb;
    for(int i=1; i<=M; i++){
        cin >> ta >> tb;
        a[ta][tb] = 1;
        a[tb][ta] = 1;
    }
    cout<<V<<" ";
    ch[V] = true;
    DFS(V);
    cout<<endl;
    memset(ch, false, sizeof(ch));

    BFS(V);
    cout<<endl;
    return 0;
}

소감

BFS를 할 때에 중복된 값들을 제거하는 부분에서 조건을 완벽하게 적지 않았기 때문에 런타임오류가 발생하였다. 자주 할 수 있는 실수이니 체크해야한다.