[백준] 1260번: DFS와 BFS 풀이 및 해설(C++)

 

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

1260번: DFS와 BFS

 

C++로 작성한 백준 문제 1260번 DFS와 BFS에 대한 문제 풀이다.

실버 2 문제로 그래프 탐색, 그래프 이론, 너비우선탐색, 깊이우선탐색이 문제를 푸는데 필요한 주요 지식이다.

 

 

---

문제 설명

문제

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

입력

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

출력

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

 

---

문제 파악하기

1. 문제 그대로 주어진 값으로 DFS 한번, BFS 한번 실행하면 된다.

 

 

 

 

 

---

 

코드 및 설명

#include <iostream>
#include <algorithm>
#include <queue>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

    int a,b,n,m,v;
    queue<int> q;
    int arr[1001][1001];
    int checked[1001];
    int visited[1001];

void dfs(int pos){
    cout<<pos<<' ';
        for(int i=1; i<=n; i++){
            if(arr[pos][i] && !checked[i]){
                checked[i]=1;
                dfs(i);
            }
        }


}

void bfs(int pos){
    q.push(pos);
    while(!q.empty()){
        pos=q.front();
        cout<<pos<<' ';
        q.pop();

        for(int i=1; i<=n; i++){
            if(arr[pos][i] && !visited[i]){
                visited[i]=1;
                q.push(i);

            }
        }

    }

}



int main(){

    cin>>n>>m>>v;

    for(int i=0; i<m; i++){
        cin>>a>>b;
        arr[a][b]=1;
        arr[b][a]=1;
    }
    checked[v]=1;
    dfs(v);
    cout<<'\n';
    visited[v]=1;
    bfs(v);

    

    return 0;
}

 

이차원 배열로 입력값을 받고, DFS한번 BFS 한번 실행시켜 준다.

BFS 실행 전 DFS로 오염된 2차원 배열을 리셋하기 귀찮아서 그냥 배열을 2개 만들었다.

최초의 점을 중복으로 방문하는 걸 막기 위해서 처음 점은 이미 방문했다고 기록하고 시작했다.

main 함수를 깔끔하게 하기 위해서 어차피 다 탐색해야 하는 거 for문을 함수 안에다가 넣어주었다.

BFS 함수는 큐를 이용한 선입선출을 통해 만들어주었다.

 

---

 

헤매었던 부분

딱히 없다.

 

 

 

 

 

---

 

마무리

BFS와 DFS에 대한 기초 문제였다