1260번-DFS와 BFS

중요 지식

---

DFS - 깊이 우선 탐색으로 불리며, 깊은 단계에 목표가 있을 경우 빠르고, 저장공간의 수요가 적다.

BFS - 너비 우선 탐색으로 불리며, 목표까지의 최단 거리를 구할 수 있지만, 노드가 많다면 저장공간을 많이 차지한다

fill_n() - 그래프의 방문리스트(visited)를 재사용하기 위해 전체적으로 초기화해야 한다 . 

find() - 작은 것부터 탐색해야 하므로 정렬이 필요하다.

 

코드

---

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define MAX 10010

vector<int> graph[MAX];
bool visited[MAX];

void dfs(int node){
    visited[node] = true;
	printf("%d ", node);

	for (int i = 0; i < graph[node].size(); i++){
		int n = graph[node][i];
        
        if(!visited[n]) dfs(n); 
	}
}

void bfs(int root){
    queue<int> que;    

    que.push(root);
    visited[root] = true;

    while(!que.empty()){
        int r = que.front();
        que.pop();
        
        printf("%d ", r);

        for (int i = 0; i < graph[r].size(); i++){
            int n = graph[r][i];

            if(!visited[n]) {
                que.push(n);
                visited[n] = true;
            }
        }
    }
}

int main(){
    int N, M, V;

    cin >> N >> M >> V;

    for(int i = 0; i < M; i++){
        int vert, link;
        cin >> vert >> link;

        if(find(graph[vert].begin(), graph[vert].end(), link) == graph[vert].end())
            graph[vert].push_back(link);
        if(find(graph[link].begin(), graph[link].end(), vert) == graph[link].end())
            graph[link].push_back(vert);
    }
    for(int i = 0; i < M; i++)
        sort(graph[i].begin(), graph[i].end());

    dfs(V);
    cout << '\n';
    fill_n(visited, MAX, false);
    bfs(V);

    return 0;
}

풀이

---

DFS 알고리즘 (재귀)

1. 인자로 노드를 입력 받는다

2. 해당 노드에 방문체크를 한다 +출력

3-1. 다른 인접한 노드를 탐색한다

3-2. 아직 방문하지 않은 노드라면 해당 노드를 인자로 재귀호출한다   

 

BFS 알고리즘 (큐)

1. 인자로 노드를 입력 받는다

2. 해당 노드를 큐에 삽입하고, 방문체크를 한다 +출력

3-1. 큐에 최하단에 있는 노드를 꺼내고(front), 해당 노드의 인접한 노드를 탐색한다

3-2. 방문하지 않은 노드라면 큐에 삽입하고, 방문체크를 한다 +출력

3-3. 큐가 빌 때까지 3번을 반복한다 

 

주의점

1. 양방향 그래프이므로 "1 3"을 입력 받을 때 1노드 뿐만 아니라 3노드에도 연결해주어야 한다 

2. 그래프 탐색중 방문할 수 있는 노드가 여러개인 경우 작은 것부터 해야 하므로 오름차순 정렬을 하고,

DFS에 경우 스택 특성상 넣고, 꺼낼 때 값이 반대로 되기 때문에 작은 것부터 꺼낼 수 있도록 반대로 넣어줘야 한다 .