BOJ 1260 DFS와 BFS

문제출처 : https://www.acmicpc.net/problem/1260

1. 문제요약

- dfs와 bfs 방문순서

- dfs 방문순서 출력 후

  bfs 방문순서 출력

2. 접근방법

- dfs, bfs

3. 시간복잡도

- O(VE)

4. 회고

- 다른사람보다 시간이 걸린이유는

  1) 입력 시간

  2) 다른사람은 자료구조로 인접리스트를 썻고, 나는 인접행렬을 썼음

     난 출력이 순서대로 나와야 하기에 인접행렬을 인덱스로 검색하면 자동으로 순서가 되므로 인접행렬을 씀

     인접리스트를 쓴 다른사람들은 sort 함

소스코드

#include<iostream>
#include<queue>
using namespace std;

int v, e, s, map[1001][1001], check[1001];

void dfs(int now){
	check[now] = true;
	cout << now << " ";

	for (int i = 1; i < v + 1; i++){
		if (!check[i] && map[now][i])
			dfs(i);
	}
}

int main(void){
	cin >> v >> e >> s;
	int a, b;
	for (int i = 0; i < e; i++){
		cin >> a >> b;
		map[a][b] = map[b][a] = 1;
	}

	dfs(s);

	for (int i = 0; i < v + 1; i++)
		check[i] = false;

	cout << "\n";
	queue<int> q;
	q.push(s);
	check[s] = true;
	while (!q.empty()){
		int now = q.front();
		q.pop();
		cout << now << " ";

		for (int i = 1; i < v + 1; i++){
			if (!check[i] && map[now][i]){
				q.push(i);
				check[i] = true;
			}
		}
	}
	cout << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]