[2022 1학기] 1주차 - DFS, BFS

1. DFS, BFS란?

그래프 탐색: 하나의 정점으로부터 시작해서 차례대로 모든 정점을 한 번씩 방문하는 것

DFS와 BFS는 그래프 탐색의 일종

 

2. 동작 방식

DFS: 깊이우선탐색 stack이나 재귀함수를 이용함. 루트 노드에서 시작해서 해당 노드의 자식 노드를 먼저 탐색

      이동할 때마다 가중치가 있거나 이동 과정에서 제약이 있는 경우

BFS: 너비우선탐색 queue를 이용함. 루트 노드에서 시작해서 해당 노드의 인접 노드를 우선적으로 탐색

      단순 최단 경로를 찾는 문제

 

3. 코드

//1차원 DFS

vector<int> adj[1010];
bool visited[1010]; //dfs방문


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

	for (int i = 0; i < adj[now].size(); i++) {
		int next = adj[now][i];
		if (!visited[next])
			dfs(next);
	}
}


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

	for (int next : adj[now]) {
		if (visited[next]) continue;
		dfs(next)
	}
}

//1차원 BFS


queue<int> q;
vector<int> adj[1010];

void bfs(int start) {
	visited[start] = true;
	q.push(start);

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

		for (int i = 0; i < adj[now].size(); i++) {
			int next = adj[now][i];

			if (!Bvisited[next]) {
				Bvisited[next] = true;
				q.push(next);
			}
		}
	}
}


void bfs(int start) {
	visited[start] = true;
	q.push(start);

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

		for (int next : adj[now]) {
			if (visited[next]) continue;
			visited[next] = 1;
			q.push(next);
		}
	}
}

//2차원

bool visited[26][26];
vector<int> adj[26];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 }; 

void dfs(int x, int y) {
	visited[x][y] = true;

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (0 <= nx && nx < N && 0 <= ny && ny < N && !visited[nx][ny] && map[nx][ny]) {
			visited[nx][ny] = true;
			cnt++;
			dfs(nx, ny);
		}
	}

}

queue<pair<int, int>> q;
void bfs(int x, int y) {

	visited[x][y] = true;
	q.push({ x, y });
	cnt[x][y]++;


	while (!q.empty()) {
		int xx = q.front().first;
		int yy = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = xx + dx[i];
			int ny = yy + dy[i];

			if (0 <= nx && nx < N && 0 <= ny && ny < M && !visited[nx][ny] && map[nx][ny] == 1) {
				visited[nx][ny] = true;
				q.push({ nx, ny });

				cnt[nx][ny] = cnt[xx][yy] + 1;
			}
		}
	}


}

 

※공부 중 작성한 내용이기에 틀린 부분이 있을 수도 있습니다!