[알고리즘] DFS (깊이 우선 탐색), BFS(너비 우선 탐색)

포인트

• 깊이 우선 탐색은 재귀를 주로 사용합니다. 저는 용어를 나누어서 사용해서 헷갈리는 부분이 많았던 것 같습니다. 
  • 깊이 우선 탐색과 너비 우선 탐색은 그렇게 다르지 않다.
• 사실 계속해서 알고리즘 공부를 하면서 생각이 나는 것은 사실 엄청 모르고 있는 것들이 깨어나간다라는 생각이 많이 든다.

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> map;
vector<bool> visited;
int n, m;
int u, v;

void dfs(int x) { //기본적으로 재귀를 사용한다고 하면 생각하기 쉽다.
	visited[x] = true; //bfs 처럼 방문 배열 표시를 하고 
	cout << x << ' ';
	for(auto ele : map[x]) { //가지고 있는 맵에서 확인을 한다. 
		if (visited[ele]) continue; //방문을 했으면 방문 안하고 
		dfs (ele); //재귀
	}
}

int main() {
	cin >> n >> m;
	map.resize(n + 1);
	visited.resize(n + 1);
	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		map[u].push_back(v);
	}
	dfs(1);
}

 

# 2020 12 04

중복 내용을 가지고 올라왔습니다. 

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> map;
vector<bool> visited;

int n, m, u, v;

void dfs(int current){
    visited[current] = 1;
    cout<<current<<' ';

    for(int i=0; i<map[current].size(); i++){
        int nx = map[current][i];
        if(visited[nx]) continue;
        dfs(nx);
    }
}

int main(){
    cin>>n>>m;
    map.resize(n+1);
    visited.resize(n+1);

    for(int i=0; i<m; i++){
        cin>>u>>v;
        map[u].push_back(v);
    }

    dfs(1);
}

#2021 03 02

공부를 하면서 반복의 중요성을 한번 더 느끼는 시간인 것 같습니다. 막상 배울 때는 모르는 것들이 연결되는 느낌이네요!

def bfs() -> int:
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]  # 방향델타를 이용한다.
    visited = [[0] * n for _ in range(n)]
    q = [start]  # 스택에 넣어준다.
    visited[start[0]][start[1]] = 1  # 방문 표시를 한다

    while q:  # 스택을 이용한 dfs
        x, y = q.pop(0)
        if data[x][y] == '3':  # 도착하면 1 반환
            return 1

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if not (0 <= nx < n and 0 <= ny < n):  # 범위 제한
                continue
            if visited[nx][ny] == 0 and data[nx][ny] != '1':  # 방문하지 않고 1이 아닐때
                q.append([nx, ny])
                visited[nx][ny] = 1

    return 0  # 도착 못하면 0 반환


def dfs() -> int:
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]  # 방향델타를 이용한다.
    visited = [[0] * n for _ in range(n)]
    stack = [start]  # 스택에 넣어준다.
    visited[start[0]][start[1]] = 1  # 방문 표시를 한다

    while stack:  # 스택을 이용한 dfs
        x, y = stack.pop(-1)
        if data[x][y] == '3':  # 도착하면 1 반환
            return 1

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if not (0 <= nx < n and 0 <= ny < n):  # 범위 제한
                continue
            if visited[nx][ny] == 0 and data[nx][ny] != '1':  # 방문하지 않고 1이 아닐때
                stack.append([nx, ny])
                visited[nx][ny] = 1

    return 0  # 도착 못하면 0 반환

def dfs2(start: list):
    global result
    x, y = start[0], start[1]
    if data[x][y] == '3':
        result = 1
        return

    visited[x][y] = 1
    for i in range(4):
        nx = x + dy[i]
        ny = y + dx[i]
        if not (0 <= nx < n and 0 <= ny < n):
            continue
        if not (0 <= nx < n and 0 <= ny < n):
            continue
        if visited[nx][ny] == 0 and data[nx][ny] != '1':
            dfs2([nx, ny])