ray

ray

매일의 HIGHLIGHT를 찾아서 ✨

[백준] 1260 DFS와 BFS (C++)

Posted on Mar 8, 2021 #DFS/BFS   #Algorithm  

1260 | DFS와 BFS

🙋‍♀️ 문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

🙌 입출력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

🙋‍♂️ 예제 입출력

4 5 1
1 2
1 3
1 4
2 4
3 4

1 2 4 3
1 2 3 4

🚀 코드

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

int n, m, v = 0;
vector<int> graph[1001];
vector<int> visit(1001);

void rDFS(int i) {
	cout << i << ' ';
	visit[i] = 1;

	for (int j = 0; j < graph[i].size(); j++) {
		int tmp = graph[i][j];
		if (visit[tmp] != 1) {
			rDFS(tmp);
		}
	}
}

void BFS(int i) {
	queue<int> que;
	que.push(i);
	visit[i] = 1;

	while (!que.empty()) {
		int tmp = que.front();
		que.pop();
		cout << tmp << ' ';
		for (int j = 0; j < graph[tmp].size(); j++) {
			if (visit[graph[tmp][j]] != 1) {
				que.push(graph[tmp][j]);
				visit[graph[tmp][j]] = 1;
			}
		}
	}

}

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

	cin >> n >> m >> v;
	int from, to = 0;
	for (int i = 0; i < m; i++) {
		cin >> from >> to;
		graph[from].push_back(to);
		graph[to].push_back(from);
	}
	for (int i = 0; i < n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}
	rDFS(v);
	for (int i = 1; i <= n; i++) {
		visit[i] = 0;
	}
	cout << "\n";
	BFS(v);

	return 0;
}

🌠 메모

문제에서 가볍게 DFS를 사용한 적은 많았어도 정석대로 구현하는거는 알고리즘 수업 이후로 처음이라 약간 헤맸다.

DFS는

처음부터 재귀를 사용해서 구해보려고 했는데, 문제에서 사용하던 방식대로 재귀를 짜니까 종료 조건이 제대로 안먹혀서 무한루프를 돌았다. (신기하게 출력은 순서대로 잘 나왔다.)

수정한 위의 코드는, 함수가 호출되면 바로 출력을 하고 visit[i] = 1 로 할당한다. 이후, 해당 정점에서 도달할 수 있는 정점들을 for문을 통해 차례로 방문하는데, 방문하지 않은 정점을 발견하면 바로 함수를 호출한다.

BFS는

DFS보다는 조금 복잡하게 구현을 할 수 밖에 없는데, 넓이 우선 탐색이므로 깊이 1인 정점들을 다 탐색후 다시 돌아와서 그 다음 깊이의 정점들을 탐색한다. 따라서 queue를 사용한다.

큐에는 다시 돌아가서 탐색을 마저 해야하는 정점들을 차례로 삽입한다. 큐에 삽입한 후에는, visit[i] = 1로 할당해 재방문을 막는다.

while문에서는 큐에 들어있는 정점들을 하나씩 확인하는데, front()를 하나 꺼내고, 해당 정점에서 갈 수 있는 정점들을 for문을 통해 하나씩 확인한다. 이때 따로 출력은 하지 않고 큐에 삽입만 하고 해당 정점이 큐에서 나왔을 때 출력한다.



# 카테고리