백준 1260 DFS와 BFS (C++)

안유태·2022년 11월 16일
0

알고리즘

목록 보기
78/239

1260번: DFS와 BFS

dfs와 bfs를 할 줄 아는가 묻는 문제이다. 정점과의 연결을 벡터로 저장해주고 dfs와 bfs를 돌려주었다. 현재 정점과 연결된 정점이 여러 개인 경우 번호가 작은 정점부터 방문하도록 오름차순으로 정렬을 해주었다. dfs와 bfs를 돌면서 도착한 정점을 차례대로 출력해주었다.
간단한 문제였다. 처음 정렬을 해주는 부분에서 범위 설정을 잘못해주어 시간을 낭비했다. 주의하자.



#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

int N, M, V;
vector<int> v[1001];
vector<int> tmp[1001];
bool visit[1001];

void dfs(int n) {
	for (int i = 0; i < v[n].size(); i++) {
		if (visit[v[n][i]]) continue;

		cout << v[n][i] << " ";
		visit[v[n][i]] = true;
		dfs(v[n][i]);
	}
}

void bfs() {
	queue<int> q;

	q.push(V);
	visit[V] = true;
	cout << V << " ";

	while (!q.empty()) {
		int n = q.front();

		q.pop();

		for (int i = 0; i < v[n].size(); i++) {
			if (visit[v[n][i]]) continue;

			q.push(v[n][i]);
			visit[v[n][i]] = true;
			cout << v[n][i] << " ";
		}
	}
}

void solution() {
	for (int i = 1; i <= N; i++) {
		sort(v[i].begin(), v[i].end());
	}

	cout << V << " ";
	visit[V] = true;
	dfs(V);

	cout << "\n";

	memset(visit, 0, sizeof(visit));
	bfs();
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M >> V;

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	solution();
	
	return 0;
}
profile
공부하는 개발자

0개의 댓글