[C++] BOJ 1260번: DFS와 BFS

문제

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

 

입력

4 5 1
1 2
1 3
1 4
2 4
3 4

출력

1 2 4 3
1 2 3 4

 

코드

#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
using namespace std;

// 1260번 DFS와 BFS

//깊이 우선 탐색
void dfs(vector<int> inputGraph[], bool *visited,int index) {
	visited[index] = true;		//방문했음을 표시
	cout << index<<" ";
	//dfs 탐색 순서
	int grphSize = inputGraph[index].size();
	for (int i = 0; i < grphSize; i++) {
		int connectIdx = inputGraph[index][i];
		if (!visited[connectIdx])
			dfs(inputGraph, visited, connectIdx);
	}
}

//너비 우선 탐색
void bfs(vector<int> inputGraph[],bool *visited,int index) {
	queue<int> que;
	que.push(index);
	visited[index] = true;
	//bfs 탐색 순서
	while (!que.empty()) {
		int visitIdx = que.front();
		que.pop();
		cout << visitIdx<<" ";
		int grphSize = inputGraph[visitIdx].size();
		for (int i = 0; i < grphSize; i++) {
			//방문한 Idx와 연결된 원소들을 que에 넣기
			int connectIdx = inputGraph[visitIdx][i];
			if (!visited[connectIdx]) {		//만약 연결된 원소를 방문하지 않았다면
				que.push(connectIdx);		//방문할 노드로 선정
				visited[connectIdx] = true;
			}
		}
	}
	
	
}

int main() {

	int N, M, V;		//정점의 개수, 간선의 개수, 탐색을 시작할 정점의 번호

	cin >> N >> M >> V;

	int size = N + 1;
	//N개만큼의 배열 만들기
	bool* visited = new bool[size] {false, };			//방문 유무를 저장하는 배열
	vector<int>* graph = new vector<int>[size];
	graph->push_back(1);

	for (int i = 0; i < M; i++) {
		int origin, connect;
		cin >> origin >> connect;
		graph[origin].push_back(connect);
		graph[connect].push_back(origin);
	}

	//정렬
	for (int i = 0; i < size; i++) {
		sort(graph[i].begin(),graph[i].end());
	}

	dfs(graph,visited, V);
	cout << endl;
	visited = new bool[size]{ false, };		//방문유무를 다시 초기화해줌(재사용 위해)
	bfs(graph, visited,V);

	delete [] visited;		//메모리 해제 
	//vector 메모리 해제
	graph->clear();
	vector<int>().swap(*graph);

	return 0;
}

 

*간단한 해설*

DFS와 BFS를 구현하였다. DFS는 모든 노드를 탐색하도록 작성하였고, BFS는 연결된 노드를 통해서 해당 노드와 연결된 노드 중 방문하지 않은 노드만 다시 탐색해서 탐색이 끝나면 종료되도록 작성하였다. DFS와 BFS의 경우 

https://better-tomorrow.tistory.com/entry/DFS-BFS-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

DFS & BFS 이해하기 및 구현(C++)

해당 포스팅을 통해 자세하게 배울 수 있었다. DFS와 BFS에 대해 알고싶으면 위의 블로그를 참조하면 좋을듯하다.

for (int i = 0; i < M; i++) {
    int origin, connect;
    cin >> origin >> connect;
    graph[origin].push_back(connect);
    graph[connect].push_back(origin);
}

연결된 노드들을 입력받는 과정에서 연결된 2개를 입력 받을시 서로 각자의 노드에 연결 정보를 입력시키도록 한다.

//정렬
for (int i = 0; i < size; i++) {
    sort(graph[i].begin(),graph[i].end());
}

입력시킨 정보들을 sort를 통해 정렬을 시켜준다. 정렬을 하지 않으면 원하는대로 결과값이 나오지 않기 때문에 정렬을 꼭 해준다.

 

 

 

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*