백준 1260 DFS와 BFS

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 정점의 개수와 정점들 사이의 간선들을 입력받고(양방향) DFS와 BFS로 탐색하였을 경우의 경로를 각각 출력하는 문제입니다.

 

DFS(깊이 우선 탐색)는 재귀함수를 이용하여 구현하였고, BFS(너비 우선 탐색)는 큐를 이용하여서 구현하였습니다. 

 

정점들 사이의 인접관계를 표시해주는 배열과 정점의 방문 여부를 알기위한 배열이 각각 필요합니다.

 

다음은 코드입니다.

 

 #include <iostream>
#include <queue>


int adjacent[1002][1002]; //정점들 사이의 인접관계를 표현하기 위한 배열 
int visited[1002]; //방문 여부를 알기위한 배열 

using namespace std;

queue<int> q;

void dfs(int v, int N) {
	visited[v] = 1;
	cout<<v<<" ";
	
	for(int i = 1; i <= N; i++) {
		if(adjacent[v][i] && visited[i] == 0) 
			dfs(i, N);
	}
}

void bfs(int v, int N) {
	q.push(v);
	visited[v] = 1;
	
	while(!q.empty()) {
	for(int i = 1; i <= N; i++) {
		if(adjacent[q.front()][i] && visited[i] == 0) {
			q.push(i);
			visited[i] = 1;
		}
	}
		cout<<q.front()<<" ";
		q.pop();
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N,M,V;
	cin >> N >> M >> V;
	
	for(int i = 0; i < M; i++) {
		int to,from;
		cin >> to >> from;
		adjacent[to][from] = 1;
		adjacent[from][to] = 1;
	}
	
	dfs(V, N);
	fill_n(visited, 1002, 0);
	cout<<'\n';
	bfs(V, N);
	
	return 0;
}