백준 1260번: DFS와 BFS (c++)

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

1260번: DFS와 BFS

---

문제 해석

 조건에 맞게 DFS와 BFS를 구현하면 되는 문제이다.

---

풀이

 이 문제에서 주의해야 할 점은 두 가지이다.

1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문
2. DFS 실행 후 방문을 체크하는 배열(visited)을 false로 초기화 후 BFS 실행

1번 해결 : graph를 정렬하여 번호가 작은 것부터 방문하도록 하였다.2번 해결 : fill함수를 사용하여 visited 배열을 false로 초기화하였다.

 

 이전 글에 DFS와 BFS에 대한 설명을 백준 1260번 기반으로 적었다.

 DFS : https://085a.tistory.com/9

 BFS : https://085a.tistory.com/10

---

코드

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

using namespace std;

int N, M, V;
bool visited[1001];
vector<int> graph[1001];
queue<int> q;

void dfs(int start) {
	if (visited[start]) return;
	visited[start] = true;
	cout << start << " ";
	int size = graph[start].size();
	for (int i = 0; i < size; i++) {
		int next = graph[start][i];
		dfs(next);
	}
}

void bfs(int start) {
	q.push(start);
	visited[start] = true;
	while (!q.empty()) {
		int s = q.front();
		q.pop();
		cout << s << " ";
		int size = graph[s].size();
		for (int i = 0; i < size; i++) {
			int next = graph[s][i];
			if (!visited[next]) {
				q.push(next);
				visited[next] = true;
			}
		}
	}
}


int main() {
	cin >> N >> M >> V;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	for (int i = 1; i <= N; i++) {
		sort(graph[i].begin(), graph[i].end());
	}
	dfs(V);
	fill(visited, visited + 1001, false);
	cout << "\n";
	bfs(V);


	return 0;
}

---

결과

---

잘못된 내용이 있다면 알려주세요!