[C++] 1260 : DFS와 BFS

실버Ⅱ

 

제목대로 DFS와 BFS

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

using namespace std;

int n;
int g[1001][1001] = { 0, };
int check1[1001] = { 0, };
int check2[1001] = { 0, };

void dfs(int here) {
	if (check1[here]) return;

	check1[here] = 1;
	printf("%d ", here);

	for (int next = 1; next <= n; next++) 
		if (g[here][next] == 1 && !check1[next]) 
			dfs(next);
}

void bfs(int here) {
	queue <int> q;
	q.push(here);
	check2[here] = 1;

	//큐에 원소가 없을 때 까지 진행
	while (!q.empty()) {
		int f = q.front();
		q.pop();	
		printf("%d ", f);

		//i(노드들) 조사 들어감
		for (int i = 1; i <= n; i++) {
			//방금 꺼낸 노드랑 조사중인 노드랑 이어져 있고 아직 이 노드 탐색 안했다면
			if (g[f][i] && !check2[i]) {
				//탐색했다 표시해 주고
				check2[i] = 1;
				//큐에 넣어준다
				q.push(i);
			}
		}
	}
}

int main() {
	int m, v;
	scanf("%d%d%d", &n, &m, &v);

	int a, b;
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &a, &b);
		g[a][b] = 1;
		g[b][a] = 1;
	}
	
	dfs(v);
	printf("\n");
	bfs(v);
}

DFS와 BFS의 정석!

BFS는 이걸로 처음 풀어봤다

 

큐에서 노드들을 뽑을 때 BFS를 정렬했던 순서대로 뽑으므로

큐에서 노드들을 뽑을 때 뽑은 노드를 출력하도록 했다

 

이제 BFS 문제들도 이걸 응용해서 풀어나가야겠다

익숙해질 때까지 시간이 걸리겠지?