백준 1260번을 풀다가, 스택이랑 큐만 전환시키면 DFS에서 BFS로 서로 왔다갔다 할 수 있었으면 좋겠다는 생각이 들었다.

그러면 구현 방법을 따로 외울 필요가 없어지니 편리할 것 같았다.

백준 1260번: DFS와 BFS
https://www.acmicpc.net/problem/1260

1. BFS

먼저 BFS 코드를 보자.

while문 안에서 큐를 이용하여 순회하는 것을 볼 수 있다.

...

void bfs(int R)
{
	queue<int> q;
	q.push(R);
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		for (auto& it : graph[cur])
		{
			if (visited[it] == false)
			{
				visited[it] = true;
				q.push(it);
			}
		}
	}
}

int main(void)
{
	...

	int R = 1; // 시작점

	graph[0].insert(R); // 가상의 간선

	bfs(0);
	return 0;
}

가상의 간선 0->R을 이용하여 정점 R부터 visited에 찍히는 방식으로 구현하였다.

2. 비재귀 DFS

이번에는 DFS 코드를 보자.

while문에 스택을 이용해서 순회하도록 구성하였다.

...

void dfs(int R)
{
	stack<int> s;
	s.push(R);
	while (!s.empty())
	{
		int cur = s.top();
		s.pop();
		for (auto& it : graph[cur])
		{
			if (visited[it] == false)
			{
				visited[it] = true;
				s.push(cur);		// A
				s.push(it);
				break;				// B
			}
		}
	}
}

int main(void)
{
	...

	int R = 1; // 시작점

	graph[0].insert(R); // 가상의 간선

	dfs(0);
	return 0;
}

코드를 자세히 보면 위에서 구현한 BFS 코드와 거의 유사한 것을 볼 수 있다.

스택-큐 차이를 제외하면 딱 두 줄이 더 추가된다. 각 라인 우측에 A, B로 표시해놓았다.

B는 다음 지점으로 점프하여 순회하기 위해서,
A는 다음 지점에서 순회가 끝나면 현재 지점으로 돌아오기 위해서 사용한다.

3. 개선된 비재귀 DFS

다만 위의 DFS 코드는 성능 문제가 있다.

pop을 해서 원래 지점으로 복귀했을 때, 인접 리스트를 중단했던 곳부터 다시 읽지 않고 처음부터 읽는다.

그래서 중단했던 곳부터 다시 읽게 하려면 코드를 아래와 같이 수정해주어야 한다.

...

void dfs(int R)
{
	stack<pair<int, int>> s;
	s.push({R, 0});
	while (!s.empty())
	{
		auto cur = s.top();
		s.pop();
        int node = cur.first;
        int start = cur.second;
        int size = graph[node].size();
		for (int i = start; i < size; i++)
		{
        	int it = graph[node][i];
			if (visited[it] == false)
			{
				visited[it] = true;
				s.push({node, start + 1});
				s.push({it, 0});
				break;
			}
		}
	}
}

int main(void)
{
	...

	int R = 1; // 시작점

	graph[0].insert(R); // 가상의 간선

	dfs(0);
	return 0;
}

pair를 이용하여 복귀 시 재개할 지점을 저장하도록 하였다.

원래 의도했던 BFS와의 코드 유사도는 조금 멀어졌지만 달리 방법이 없었다.

참고

https://www.acmicpc.net/board/view/117573
https://gist.github.com/Baekjoon/d2e726b5f85bd8c17200