[백준] 1260 DFS와 BFS - dfs, bfs

[ 문제링크 ]

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

 

🚩 조건

1. 그래프를 DFS, BFS로 탐색한 결과를 각각 출력해라.
2. 방문할 수 있는 정점이 여러 개이면 정점 번호가 작은 것을 먼저 방문해야 함
3. 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000)
4. 입력으로 주어지는 간선은 양방향

 

 

🚩 접근

2 -> 입력을 모두 저장한 후 sort 함수를 이용하여 오름차순으로 정렬

DFS -> stack

BFS -> queue

 

 

🚩 시행착오

• memset(시작 포인터, 설정할 값, 크기) : cstring 헤더파일 필요
  • ex. memset(visit, false, sizeof(visit))

 

ㅎ..

• 컴파일 에러 - sort 함수 사용시 algorithm 헤더파일 필요, bool을 boolean으로 오타
• 컴파일 에러(Segfault) - v[0]은 버리는 vector여서 비어있는데 for문에서 0부터 시작함
• 시간초과 - bfs 구현시 일단 다 push한 후 visit과 비교하며 pop/재귀하도록 했는데, 이 부분에서 시간초과가 발생한 것으로 예상하여 push 전 visit 여부를 확인하도록 수정. 그리고 queue.front()를 호출하기 전 반드시 empty 여부 확인해야함.(런타임 에러 나서 시간초과가 발생하는 듯)
• 출력 형식 문제 - 출력 마지막에 공백/줄바꿈 있어도 상관 없음 but 없으면 상관있나봐

 

 

💻 코드 (C++)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

vector<int> v[1001];    // 각 노드의 간선 저장
bool visit[1001];
queue<int> q;

void dfs(int start){
    cout<<start<<" ";
    visit[start] = true;
    for(int i=0;i<v[start].size();i++){
        int next = v[start][i];
        if(visit[next]) continue;
        dfs(next);
    }
}

void bfs(int start){
    cout<<start<<" ";
    visit[start] = true;
    for(int i=0;i<v[start].size();i++){
        int next = v[start][i];
        if(visit[next]) continue;
        q.push(next);
    }
    while(!q.empty() && visit[q.front()]){
        q.pop();
    }
    
    if(!q.empty())
        bfs(q.front());
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N,M,V,a,b;
    cin>>N>>M>>V;
    for(int i=0;i<M;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1;i<=N;i++){
        sort(v[i].begin(), v[i].end());
    }
    
    dfs(V);
    memset(visit, false, sizeof(visit));
    cout<<"\n";
    bfs(V);
}