BOJ/백준 - 1260 DFS와 BFS

DFS

- 깊이 우선 탐색,

- 모든 노드 맹목적 탐색,

- 스택으로 구현하는데 굳이 스택으로 하지 않고 재귀로 해도 자연스럽게 스택처럼 사용 가능.(스택으로 굴러가서)

 

BFS

- 너비 우선 탐색

- 최단경로, 미로찾기

- FIFO, Queue 사용.

 

* dfs나 bfs모두 방문했는지 안했는지 체크하는 걸 잊지 말자.

 

 

구현은 아랫쪽 주석에 자세히 적어놓았다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define NMAX 1001
#define MMAX 10001
using namespace std;
int N, M, V;
int visit[NMAX];
vector<int> G[NMAX];
 
void dfs(int v) { //정점 v방문
    visit[v] = 1; //정점 v방문함을 표시해줌.
    cout << v << " "; //방문한 정점 출력
    int vsize = G[v].size(); //v정점에 연결된 다른 정점들의 수(간선 수)
    
    for (int i = 0; i < vsize; i++) { //v정점에 연결된 다른 정점들의 수만큼 for문
        int nxt = G[v][i]; //다음 방문할 정점
        if (visit[nxt]) continue; //만약 이미 방문했었던 정점이라면 continue;
        dfs(nxt);// 그렇지 않다면 정점 v방문
    }
}
 
void init_visit() { //visit배열 초기화
    for (int i = 1; i <= N; i++) {
        visit[i] = 0;
    }
}
 
void bfs() {
    queue<int> q;
    q.push(V); //정점 V를 push
    visit[V] = 1; //정점 V에 방문했음을 표시한다.
 
    while (!q.empty()) {
        int cur = q.front(); //가장 앞에 있는 정점
        cout << cur << " "; //출력
        q.pop(); //꺼내줌
 
        int vsize = G[cur].size(); //현재 cur정점에 연결되어있는 다른 정점(간선들)의 수
        for (int i = 0; i < vsize; i++) {
            int nxt = G[cur][i]; //다음 정점
            if (visit[nxt]) continue; //이미 방문한 정점이라면 continue
            q.push(nxt); //아니라면 push해줌
            visit[nxt] = 1; //방문함을 표시해준다.
        }
    }
}
 
 
int main(void) {
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    cin >> N >> M >> V;
 
    for (int i = 0; i < M ; i++) {
        int u, v;
        cin >> u >> v;
        //양방향 연결
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    //정점 번호가 작은 것부터 방문
    for (int i = 0; i < N; i++) {
        sort(G[i].begin(), G[i].end());
    }
 
    dfs(V);
    init_visit();
    cout << "\n";
    bfs();
 
    return 0;
}