DFS와 BFS : (2) 구현하기

#   자료구조 복습

Stack	Queue
LIFO (Last In First Out)	FIFO (First In First Out)

 

 

1.  DFS 구현

1-1.  DFS 과정

더이상 이어진 유효 노드가 없는 절벽 끝까지 쭉 탐색한다. 이때, 절벽 끝에 도달하고 나면, 스택에서 하나씩 다시 버리면서 왔던 길을 돌아가서 다른 길로 접어든다. 이후 탐색 반복

 

 

1-2.  DFS 구현 코드

1  )  재귀함수 이용

 

#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;


void dfs(int start, vector<int> graph[], bool check[]) {
    check[start] = true;
    
    while(!st.empty()) {
    	int current = st.top();  // 가장 최근에 스택 들어와있던 노드 current
        st.pop();
        
        for(int i=0 ; i<graph[current].size() ; i++) {
        	int next = graph[current][i];
                if(check[next] == false) {    // 방문한 적 없는 경우
                    dfs(next, graph, check);  // Recursion
                }
	}
    }
}

 

2  )  스택 이용

 

#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;


// dfs 함수에 인자로 들어온 노드는 방문한 것으로 취급
void dfs(int start, vector<int> graph[], bool check[]) {
	stack<int> st;
    st.push(start);
    check[start] = true;
    
    while(!st.empty()) {
    	int current = st.top();  // 가장 최근에 스택 들어와있던 노드 current
        st.pop();
        
        for(int i=0 ; i<graph[current].size() ; i++) {
        	int next = graph[current][i];
                if(check[next] == false) {  // 방문한 적 없는 경우
                    check[next] = true;
                    st.push(current);    // 17th line에서 pop했기 때문에 다시 넣기
                    st.push(next);
                    break;
                }
	}
    }
}

 

 

---

2.  BFS 구현 방법

2-1.  BFS 과정

깊이가 1, 2, 3, .... 인 모든 노드를 깊이가 작은 순서대로 방문한다. 더이상 방문할 곳이 없으면 탐색 종료 

 

 

 

2-2.  BFS 구현 코드

1  )  큐 이용

 

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;


void dfs(int start, vector<int> graph[], bool check[]) {
	queue<int> q;
    
    q.push(start);
    check[start] = true;
    
    while(!q.empty()) {
    	int tmp = q.front(); 
        q.pop();
        
        // 같은 graph[tmp] 라인에 있는 graph[tmp][i]들은 모두 같은 depth!
        for(int i=0 ; i<graph[tmp].size() ; i++) {
        	int next = graph[tmp][i];
                if(check[next] == false) {    // 방문한 적 없는 경우
                    q.push(next);
                    check[next] = true;
                }
	}
    }
}