5장. BFS/DFS

연성·2020년 9월 12일

코딩테스트

목록 보기

2/261

1장이 아니라 5장부터 시작하는 이유
- 블로그를 오늘 만들어서..ㅎ

자료구조 내용이 없는 이유
- 아는 건 안 적음

1. 꼭 필요한 자료구조

1) 스택(stack, FILO: First In Last Out)

2) 큐(queue, LIFO: Last In First Out)

3) 그래프(graph)

인접행렬
- 2차원 배열에 각 노드가 연결된 형태를 기록
- 모든 관계를 저장하기 때문에 노드 개수가 많으면 메모리 낭비가 심함

인접 리스트
- 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장
- 노드 연결을 확인하기 위해 연결된 데이터를 모두 확인해야함 -> 느림

2. 깊이 우선 탐색 (DFS: Depth First Search)

한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문 후 다시 돌아가서 다른 경로 탐색

1) 과정

1. 시작 노드를 스택에 삽입하고 방문처리
2. 스택 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문처리
3. 2번의 과정 반복

2) 시간 복잡도: O(n)

3) 소스 코드

#include <iostream>
#include <vector>

using namespace std;

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

void dfs(int x) {
	// 방문한 노드를 방문 표시
	visited[x] = true;

	for (int i = 0; i < graph[x].size(); i++) {
		// x에 연결된 가장 가까운 노드 y
		int y = graph[x][i];
		// y를 방문한 적이 없으면 dfs 재귀호출
		if (!visited[y]) dfs(y);
	}

}

3. 너비 우선 탐색 (BFS: Breath First Search)

 가까운 노드부터 탐색

1) 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문처리
2. 큐에서 노드를 꺼내 인접 노드 중 방문하지 않은 노드를 모두 큐에 넣고 방문처리
3. 2번 반목

2) 시간 복잡도

O(n) - DFS보다는 일반적으로 조금 빠름

3) 소스코드

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

using namespace std;

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

void bfs(int start){
    queue<int> q;
    q.push(start);

    visited[start] = true;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i=0; i<graph[x].size(); i++){
            int y = graph[x][i];
            if(!visited[y]){
                q.push(y);
                visited[y] = true;
            }
        }
    }
}