글 읽기 - ★★★ DFS와 BFS FAQ ★☆★☆★ DFS와 BFS FAQ ★★★

jh05013 5년 전 7

"방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고" "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고" "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고" "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고" "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고" "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고" "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고"
BFS를 할 때, 정점을 방문했다는 표시는 반드시 그 정점을 큐에 넣을 때 해야 합니다. 큐에서 뺄 때 표시를 하면 중복 방문이 일어날 수 있습니다. 왜 중복 방문이 일어날 수 있는지 알아야 BFS를 제대로 이해했다고 할 수 있지 않을까 생각됩니다.
1. 그리고 이 문제에서는 영향이 없지만, 파이썬 쓰시는 분들은 제발, 제발 list.pop(0)를 쓰지 마세요! pop(0)는 모든 재앙의 근원입니다. https://www.acmicpc.net/blog/view/70
DFS를 재귀로 구현했을 때도 마찬가지입니다. 정점을 방문했다는 표시는 반드시 그 정점에서 DFS 호출을 시작할 때 해야 합니다.
파이썬의 최대 재귀 깊이는 1,000 근처입니다. 그래서 재귀로 DFS를 구현하면 방법에 따라 런타임 에러가 날 수 있습니다. sys.setrecursionlimit으로 이 깊이를 조절할 수 있습니다.
입력으로 주어지는 간선은 양방향입니다. 즉 a b가 한 줄에 주어진다면 a에서 b로도 갈 수 있고, b에서 a로도 갈 수 있습니다.

djm03178 5년 전 1

3번은 제가 이해하기로는 스택으로 DFS를 그렇게 구현하면 재귀로 구현할 때와 결과가 달라질 것 같습니다. 스택에 넣을 때 이미 방문 체크를 해버린다면, 다른 정점을 통해 그 정점에 도달할 수 있어도 방문 체크 때문에 나아가지 못할 것 같네요.

아래 코드처럼 만드는 걸 말씀하신 걸로 보이는데, 이런 케이스를 넣으면 재귀 코드와 답이 서로 다르게 나옵니다.

4 4 1

1 2

2 3

2 4

1 3

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

vector<int> adj[1001];
bool visited[1001];

void dfs(int i)
{
	visited[i] = true;
	cout << i << ' ';
	for (int x : adj[i])
		if (!visited[x])
			dfs(x);
}

int main()
{
	int n, m, v;
	cin >> n >> m >> v;
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (int i = 1; i <= n; i++)
		sort(adj[i].begin(), adj[i].end());
	dfs(v);
	cout << '\n';
	
	memset(visited, 0, sizeof(visited));

	stack<int> s;
	s.push(v);
	visited[v] = true;

	while (!s.empty())
	{
		int i = s.top();
		s.pop();

		cout << i << ' ';
		for (int j = adj[i].size() - 1; j >= 0; j--)
		{
			int x = adj[i][j];
			if (visited[x])
				continue;
			visited[x] = true;
			s.push(x);
		}
	}
}

jh05013 5년 전 0

재귀 과정을 그대로 스택으로 구현하는 것을 생각했는데 구현량이 만만치 않겠군요. 해당 내용을 지웠습니다.

댓글을 작성하려면 로그인해야 합니다.