백준 1260(dfs와 bfs)

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

문제에 써있듯이 dfs랑 bfs를 구현할 수 있는가 묻는 단순한 문제이다. 

 

여기서 중요한것은 bfs를 할 때, vector를 이용해서 인접리스트를 만드는 것이다. 

 

vector는 push_back, pop_back이 있어서 거의 queue처럼 사용할 수 있다는 것을 알아야 한다.

처음에는 이렇게 할 수 있다는 걸 모르고, 이차원 벡터로 만들어서 풀려다가 엄청나게 헤맸다. 

 

또한 구현할 때, 

 

for(int i =0; i<v.size(); i++){

    v.back();

    ~~~

   v.pop_back();

   ~~~~~

}

 

이런 식으로 구현하게 되면 i는 증가하는데 v.size()는 감소하므로 원하는 결과가 나오지 않으므로 주의하자. 

 

 

문제 조건에서 둘 다 인접한 그래프에 대해서 오름차순으로 접근 하라고 했어서 dfs는 그냥 for문을 통해서 접근했고, bfs는 따로 정렬을 해주었다.

#include<iostream>
#include<queue>
#include<utility>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
#define MAX 1001
#define MAX2 10001

int N, M, start, a, b, tmp, tmp2;
vector<int> v[MAX];
bool mat[MAX][MAX] = { false };
bool visited[MAX] = { false };
bool visited2[MAX] = { false };
queue<int> q;

void bfs(int index) {
	q.push(index);
	visited2[index] = true;
	while (!q.empty()) {
		tmp = q.front();
		cout << tmp << " ";
		q.pop();
		while(!v[tmp].empty()){
			tmp2 = v[tmp].back();
			v[tmp].pop_back();
			if (!visited2[tmp2]) {
				q.push(tmp2);
				visited2[tmp2] = true;
			}
		}
	}
}

void dfs(int index) {
	visited[index] = true;
	cout << index << " ";
	for (int i = 1; i <= N; i++) {
		if (mat[index][i] && !visited[i]) {
			dfs(i);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> start;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		mat[a][b] = true;
		mat[b][a] = true;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for (int i = 1; i <= N; i++) {
		sort(v[i].begin(), v[i].end(), greater<int>() );
	}
	dfs(start);
	cout << "\n";
	bfs(start);
}