백준 1260_DFS와 BFS(C++)

 

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

[문제 풀이]

DFS와 BFS를 이용하여 문제를 풀었습니다.

이 문제는 그래프를 구성하는 정점과 간선이 주어질 때 그래프 탐색을 DFS와 BFS로 탐색하는 것을 구현하는 문제입니다. 따라서, DFS와 BFS 함수를 구현하여 주었습니다.

DFS 코드 설명
입력으로 주어진 간선을 저장해 둔 map 배열을 N 크기 만큼 돌면서 DFS 함수에 매개변수로 주어진 v 와 연결된 정점을 찾습니다. 연결된 정점이 방문하지 않은 곳이라면 재귀를 이용하여 DFS를 호출해주었습니다.

BFS 코드 설명
먼저 시작 정점 v를 queue에 넣어주고 입력으로 주어진 간선을 저장해 둔 map 배열을 N 크기 만큼 돌면서 v 와 연결 돼 있으면서 방문하지 않은 점을 모두 차례대로 queue에 넣어 주었습니다.

[코드]

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

using namespace std;

int N, M, V;

int map[1001][1001] = { 0, };

bool visit[10001] = { false, };

queue<int> pass_queue;

void DFS(int);
void BFS(int);

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> V;

	for (int i = 0; i < M; i++) {
		int temp1, temp2;
		cin >> temp1 >> temp2;

		map[temp1][temp2] = 1;
		map[temp2][temp1] = 1;
	}

	DFS(V);
	for (int i = 0; i <= N; i++) visit[i] = false;
	BFS(V);

	return 0;

}


void DFS(int v) {

	cout << v << " ";
	visit[v] = true;

	for (int i = 1; i <= N; i++) {

		if (i == v)
			continue;

		if (map[v][i] == 1 && map[i][v] == 1 && !visit[i])
			DFS(i);
	}

}

void BFS(int v) {

	cout << endl;
	pass_queue.push(v);
	visit[v] = true;

	while (!pass_queue.empty())
	{
		int temp = pass_queue.front();
		for (int i = 1; i <= N; i++) {

			if (map[temp][i] == 1 && map[i][temp] == 1 && !visit[i]) {
				pass_queue.push(i);
				visit[i] = true;
			}
				
		}
		cout << pass_queue.front() << " ";
		pass_queue.pop();
	}

}