[백준 1260][🤍2] DFS와 BFS

🚀 난이도

🤍 실버 2

🚀 문제

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

🚀 내 풀이 ⭕

#include <bits/stdc++.h>

using namespace std;

void DFS(vector<vector<int>>& graph, vector<bool>& checked, int now) {
	cout << now << ' '; // 방문 출력
	for (int i = 0; i < graph[now].size(); ++i) {
		int next = graph[now][i];
		if (!checked[next]) { // 방문 안한 정점이면 고고
			checked[next] = true;
			DFS(graph, checked, next);
		}
	}
}

void BFS(vector<vector<int>>& graph, vector<bool>& checked, int start) {
	queue<int> q;
	q.push(start);
	checked[start] = true;

	while (!q.empty()) {
		int now = q.front();
		q.pop();
		cout << now << ' ';  // 방문 출력
		
		for (int i = 0; i < graph[now].size(); ++i) {
			int next = graph[now][i];
			if (!checked[next]) { // 방문 안한 정점이면 고고
				checked[next] = true;
				q.push(next);
			}
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n, m, start;
	cin >> n; cin >> m; cin >> start;
	vector<vector<int>> graph(n + 1);
	for (int i = 0; i < m; ++i) {
		int v1, v2; cin >> v1; cin >> v2;
		graph[v1].push_back(v2);
		graph[v2].push_back(v1);
	}
	for (int i = 1; i <= n; ++i)
		sort(graph[i].begin(), graph[i].end()); // 정점 번호 작은 것부터 먼저 방문하라고 했기 때문에 정렬 해줌

    /* DFS */
	vector<bool> checked_dfs(n + 1); // DFS 용 방문 여부
	checked_dfs[start] = true; // 출발 지점 미리 방문 체크
	DFS(graph, checked_dfs, start); 
	cout << '\n';

    /* BFS */
	vector<bool> checked_bfs(n + 1); // BFS 용 방문 여부 
	BFS(graph, checked_bfs, start);
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기