[그래프] 1260. DFS,BFS

1. 문제 해결 전략

DFS,BFS를 알고 있느냐 없느냐의 문제.. 그리고, 시간초과를 생각해주어야 한다.

DFS는 말 그대로 그래프에서 선택된 노드를 한 방향으로 깊게 파고들어서 탐색하는 방법이고

BFS는 한 노드와 연결된 모든 노드들을 하나씩 다 탐색하는 방법이다.

 

어떤 순서로 탐색을 하냐에 따라서 시간초과가 발생하더라. 처음에 DFS 문제인줄알고 삽질하다가 BFS 문제인 것을 발견했다.  한 번에 모아서 출력을 하려 했었는데 이렇게 하면 무조건 시간초과가 뜬다. 검색이 완료될 때마다 해당 노드의 인덱스를 출력해야 한다.

 

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

using namespace std;

vector<int> v[10001];
bool b[1001] = { false, };
bool b2[1001] = { false, };
int N, M, V;
void dfs(int start)
{
	if (b[start] == true) return;

	b[start] = true;
	cout << start << " ";
	for (int i = 0; i < v[start].size(); i++)
	{
		dfs(v[start][i]);
	}
}
void bfs(int start)
{
	/*
		연결된 지점의 모든 정점을 방문한다.
		방문한 정점은 true로 잠근다.
		방문한 정점들로부터 다시 연결된 지점의 모든 정점을 방문한다.
	*/

	queue<int> q;
	q.push(start);
	b2[start] = true;
	while (!q.empty())
	{
		int front = q.front();
		q.pop();
		printf("%d ", front);
		for (int i = 0; i < v[front].size(); i++)
		{
			int y = v[front][i];
			if (b2[y] == false)
			{
				b2[y] = true;
				q.push(y);
			}
		}
	}

	printf("\n");
}

int main()
{
	cin >> N >> M >> V;
	for (int i = 0; i < M; i++)
	{
		int s, e;
		cin >> s >> e;

		v[s].push_back(e);
		v[e].push_back(s);
	}

	for (int i = 0; i < M; i++)
	{
		sort(v[i].begin(), v[i].end());
	}

	dfs(V); cout << endl;
	bfs(V);
}

Stack으로 구한 dfs

 

void dfs(int start)
{
	stack<int> s;

	s.push(start);
	cout << start << " ";
	b[start] = true;
	while (!s.empty())
	{
		int top = s.top();
		bool check = false;
		for (int i = 0; i < v[top].size(); i++)
		{
			if (b[v[top][i]] == false)
			{
				b[v[top][i]] = true;
				cout << v[top][i] << " ";
				s.push(v[top][i]);
				check = true;
				break;
			}
		}
		if (check) continue;
		if (s.size() == N) break;
		s.pop();
	}
}

오히려 dfs는 stack보다 재귀가 더 생각하기 쉬운 것 같다. 불필요한 변수처럼 보이던 것들이 2중 반복문의 특징 때문에 필요하다는 것을 오랜 시간동안 생각한 결과 알게 되었다. 각 반복문들의 탈출조건을 설계하는 것이 필요하다.

 

2. 걸린 시간

dfs( o) , bfs (x)

 

3. 느낀점

dfs를 풀 때 재귀로 풀 수 있다는 점을 인지하고 있었지만, 재귀에 자신이 없었기때문에 stack을 이용해서 풀려고 했다.

하지만, 시간초과가 났을 때 혹시 stack이 잘못됐나 싶어서 그냥 재귀로 풀었는데.. bfs 때문이었다.

 

착각을 했던게 이건 '탐색' 문제라는 것이다. 내가 정말 잘못생각했던게 한 번에 한 번씩만 방문하여 모든 노드를 방문할 수 있는 경로 라고 착각 한 것.. 절대 불가능한 그래프도 존재하고 애초에 전제가 잘못되었는데 왜 이렇게 생각했는지 모르겠다. bfs가 틀린건 이 때문인 것 같다. 그리고 다른 사람들의 코드를 보고 '어떻게 구간마다 출력을 할 수 있다는거지?' 라는 의문이 해결되었다. 결국 중복된 결과는 return 될 것이고 어떠한 방식으로도 방문만 하면 (깊이,넓이 조건만 만족시키고) 되는 간단한 문제였다.

 

여기에 시간을 많이 투자했다는 것 자체가 알고리즘 이해도가 떨어진다는 것을 말해주고 있는 것 같다 ㅜㅜ.

카카오 그래프 문제도 이렇게 쉬웠던 것같은데 하.. 더 열심히 해야겠다.

 

4. 링크

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