[C++] 1260 DFS와 BFS

1260번: DFS와 BFS (acmicpc.net)

1260번: DFS와 BFS

---

난이도 : 실버2

 

풀이과정 : 

DFS는 재귀함수를 이용해서 풀었습니다

[Algorithm] DFS 정리 (tistory.com)<< dfs 정리 참조

 

BFS는 큐를 이용해서 풀었습니다.

[Algorithm] BFS 정리 (tistory.com) << bfs 정리 참조

 

 

입력을 받을 때 (1,2)를 받았으면 1에다가 2를 추가하고 2의 노드에 1을 추가해야 합니다 (양쪽에 추가)

그리고 벡터 정렬 해줘야 합니다(for문을 이용하여 벡터를 정렬해주었습니다)

 

 

 

 

코드 :

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n, m, v;
vector<int> adj[1005];
queue<int> q;
bool visited[1005];
bool visited1[1005];

void dfs(int now) {
	visited[now] = 1;
	printf("%d ", now);
	for (int i = 0; i < adj[now].size(); i++) {
		int next = adj[now][i];
		if (!visited[next]) dfs(next);
	}
	
}
void bfs(int st) {
	q.push(st);
	visited1[st] = 1;
	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 (!visited1[next]) {
				q.push(next);
				visited1[next] = 1;
			}	
		}
	}
}
int main() {
	scanf("%d %d %d", &n, &m, &v);
	
	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	for (int j = 1; j <= n; j++) {
		sort(adj[j].begin(), adj[j].end());
	}

	dfs(v);
	printf("\n");
	bfs(v);
}