C++) 백준 1260번 풀이_DFS와 BFS

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

1260번: DFS와 BFS

그래프 서치 공부를 안한지 오조오억년이 다 되어가서 잡아본 문제

예전에 공부를 오지게 안하긴 안했구나라는 것을 뼈저리게 체감했다

 

우선.. 그래프는 2차원 int배열 또는 vector로 표현할 수 있다

처음엔 2차원 배열을 사용하려고 했는데, 저 좋은 vector container를 냅두고 왜? 라는 의문이 들어

그냥 벡터로 사용...

 

 

우선 DFS랑 BFS부터 간단하게 설명하자면

 

• DFS : Depth First Search
• BFS : Breadth First Search

그래프를 탐색할 때, 이름 그대로 깊이를 우선해서 탐색할 것인지, 너비를 우선해서 탐색할 것인지에 따라 나뉘는 탐색 방법이다. 다르게 말하자면, 땅에서 보물을 찾을 때.. 한군데만 깊이 파보고 안 나오면 다른곳을 팔 것인지, 얕게얕게 다 파볼 것인지로 나뉜다고 할 수 있다.

 

탐색 모양이 수직/수평으로 다르기 때문에, 사용해야하는 자료구조도 다름.

DFS는 스택을, BFS는 큐를 사용하게 된다

(나는.. DFS 재귀 함수 구현을 선호한다)

 

 

그래프와 시작노드가 주어졌을 때, DFS와 BFS로 탐색한 순서를 출력하면 되는 문제.

 

 

예를 들어보자!

 

 

위와 같은 그래프가 있고, 시작노드가 1이라고 할 때

 

DFS(깊이 우선 탐색)을 해보면

 

의 순서로 1 -> 2 -> 3 -> 4 -> 5 탐색을 한다.

 

 

그러나 BFS(너비 우선 탐색)의 경우,

의 순서로 1 -> 2 -> 4 -> 5 -> 3 탐색을 한다.

 

 

그렇다.

(...설명능력부족...)

 

 

---

 

무튼 그래서 스택이나 큐를 사용한 구현을 어떻게 하냐면...

 

DFS

1. 시작노드를 방문한다. (방문한 노드를 x라고 한다)

2. 시작노드에 인접한 정점 중 방문하지 않은 정점을 찾는다.

2-1. 방문하지 않은 정점 y가 있으면, x를 스택에 push하고 정점 y를 방문한다.

2-2. 방문하지 않은 정점이 없다면, 상위노드로 올라가서 인접정점을 다시 찾기 위해 스택 pop하고 다시 2로.

3. 스택이 비어있다면 종료한다.

 

 

BFS

1. 시작노드를 방문한다. (방문한 노드를 x라고 한다)

2. 시작노드에 인접한 정점 중 방문하지 않은 정점 모두 찾는다.

3. 방문하지 않은 정점 y가 있으면, y를 큐에 넣는다. 인접 노드 중 방문하지 않은 정점이 없을때까지 반복한다.

4. 큐의 앞에서 노드 z를 꺼내고(dequeue), z에 인접한 정점 중 방문하지 않은 정점을 찾는다.

4-1. 방문하지 않은 정점이 있다면, 큐에 넣는다.

4-2. 방문하지 않은 정점이 없다면, 4를 반복한다.

5. 큐가 비게된다면 종료한다.

 

 

 

를 코드로 짜면 이렇게 됩니다.

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

void dfs(int start, vector<int> graph[], bool check[])
{
	stack<int> s;

	check[start] = true;
	cout << start << " ";
	s.push(start);

	while (!s.empty())
	{
		int cur = s.top();
		s.pop();
		for (int i = 0; i < graph[cur].size(); ++i)
		{
			int next = graph[cur][i];
			if (check[next] == false)
			{
				cout << next << " ";
				check[next] = true;

				s.push(cur);
				s.push(next);
				break;
			}
		}
	}

	/* 재귀
	check[start] = true;
	cout << start <<" ";

	for (int i = 0; i < graph[start].size(); i++)
	{
		int next = graph[start][i];
		if (check[next] == false)
			dfs(next, graph, check);
	}
	*/
}

void bfs(int start, vector<int> graph[], bool check[])
{
	queue<int> q;

	q.push(start);
	check[start] = true;

	while (!q.empty()) {
		int tmp = q.front();
		q.pop();
		cout << tmp << " ";
		for (int i = 0; i < graph[tmp].size(); i++)
		{
			if (check[graph[tmp][i]] == false) {
				q.push(graph[tmp][i]);
				check[graph[tmp][i]] = true;
			}
		}
	}
}

int main()
{
	
	int n, m, start;
	cin >> n >> m >> start;
	vector<int> graph[1001];
	bool check[1001] = { false, };

	for (int i = 0; i < m; ++i)
	{
		int s, e;
		cin >> s >> e;
		graph[s].push_back(e);
		graph[e].push_back(s);

	}

	for (int i = 1; i <= n; i++)
		sort(graph[i].begin(), graph[i].end());

	dfs(start, graph, check);
	cout << endl;
	fill(check, check + 1001, false);
	bfs(start, graph, check);

}