[BOJ / C++] 1260번 - DFS와 BFS

문제

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

1260번: DFS와 BFS

풀이

dfs와 bfs에 대한 기초를 점검하는 문제이다.

그래프를 인접행렬과 인접리스트로 나타낼수 있는데, 인접행렬보다 인접리스트가 메모리 측면에서 더 좋기때문에 벡터를 이용하여 구현하였다.

입력받을때 양방향 그래프이므로 양쪽모두에 간선을 넣어주고, 각 노드 벡터마다 정렬을 해준뒤 구현하면 된다. 

 

코드

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

using namespace std;

int N,M,V;

bool isVisit[1001] = { false, };

vector<vector<int>> graph;

void dfs(int depth,int preVertex) {
	cout << preVertex << " ";
	if (depth == N) {
		return;
	}

	for (int i = 0; i < graph[preVertex].size(); i++) {
		if (!isVisit[graph[preVertex][i]]) {
			isVisit[graph[preVertex][i]] = true;
			dfs(depth+1,graph[preVertex][i]);
		}
	}

}

void bfs() {
	bool isVisit[1001] = { false, };

	queue<int> buffer;
	buffer.push(V);
	isVisit[V] = true;

	while (!buffer.empty()){
		V = buffer.front();
		buffer.pop();
		cout << V << " ";
		for (int i = 0; i < graph[V].size(); i++) {
			if (!isVisit[graph[V][i]]) {
				isVisit[graph[V][i]] = true;
				buffer.push(graph[V][i]);
			}
		}

		
	} 
	
}

int main() {
	cin >> N>>M>>V;
	graph=vector<vector<int>>(N+1);
	for (int i = 1; i <= M; i++) {
		int vertex1, vertex2;
		cin >> vertex1 >> vertex2;
		graph[vertex1].push_back(vertex2);
		graph[vertex2].push_back(vertex1);
	}
	for (int i = 1; i <= N; i++) {
		sort(graph[i].begin(), graph[i].end());
	}

	isVisit[V] = true;
	dfs(1, V);
	cout << "\n";
	bfs();
	
}