next_permutation VS back-tracking 비교

나우히즈·2024년 11월 8일

C++TROUBLESHOOTING algorithm

trialAndErrors

목록 보기

4/5

백준 17141 연구소2 문제를 풀며 배웠던 점에 대한 포스팅입니다.

이전부터 조합 구현에 대한 생각을 한 번 정리할까 싶었는데 문제를 풀면서 비교하기 딱 좋겠다 싶어서 지금 포스팅을 하게 되었습니다.

문제 설명

17141 연구소2 문제는 주어진 맵에 대해서 맵 상에 바이러스가 존재 가능한 위치를 지정해주고, 가장 빠르게 바이러스가 번지게 되는 시간이 얼마인지 구하는 문제입니다.

조합을 사용하여 바이러스가 존재할 위치를 선택해, BFS를 활용하여 최단시간을 구하는 방식을 가장 먼저 떠올렸습니다.

BFS는 일반적인 방식으로 구현했고, 조합을 구현하는 방식에 있어서 고민이 있었습니다.

방법1) 백트래킹을 통해 조합을 구현한다.
방법2) std::next_permutation 을 통해 구현한다.

우선 생각나는대로 방법 1을 선택해보았습니다.

방법1) Back Tracking

void comb(int depth, int next)
{
	if (depth == M)
	{
		int t = bfs();
		if (mapCheck())
			if (t < res)
				res = t;
		return ;
	}

	for (int i = next; i < virus.size(); i++)
	{
		cArr[depth] = virus[i];
		comb(depth + 1, next + 1);
	}
}

cArr이라는 조합에 대한 정보를 담는 배열에 바이러스의 좌표를 담아 bfs를 진행하도록 했습니다.

그 후 진행된 맵에 대해 방문하지 못한 곳이 있는지 체크하는 mapCheck() 후 최단시간을 기록하는 방법이었습니다.

생각보다 깔끔하게 구현이 되어서 통과할 줄 알았는데 시간초과가 발생하였습니다.

중복되거나 불필요한 케이스의 함수 호출로 인한 오버헤드가 원인이 되었다고 생각했습니다.

이에 오버헤드를 최소화하기 위하여, 방법2를 적용해보았습니다.

방법2) std::next_permutation


	std::vector<int> ind;
	for (int i = 0; i < M; i++)
		ind.push_back(1);
	for (int i = M; i < virus.size(); i++)
		ind.push_back(0);
	std::sort(ind.begin(), ind.end());

	do
	{
		cArr.clear();
		for (int i = 0; i < virus.size(); i++)
			if (ind[i] == 1)
				cArr.push_back({virus[i].first, virus[i].second});
		int t = bfs();
		if (mapCheck())
			if (t < res)
				res = t;
	} while (std::next_permutation(ind.begin(), ind.end()));

별도의 함수 없이 메인문에 넣고 do-while을 진행시켰습니다.
ind 라는 배열을 통해 바이러스가 들어갈 수 있는 위치에 대한 배열을 구성했고, 사용할 위치는 1이, 아닌 위치는 0이 담겨 바이러스 위치에 대한 조합을 얻어내는 방식이었습니다.

std::next_permutation은 배열의 뒤에서부터 처음으로 감소하는 요소를 찾습니다.
그 위치에서 가장 작은 값을 찾아 교환한 후, 뒤쪽 부분을 오름차순으로 정렬하여 다음 순열을 만듭니다.

예를들자면, 전체 5개의 바이러스 자리가 있고, 그 중 3개의 자리를 고른다면

ind 배열을 {1, 1, 1, 0, 0} 으로 초기 구성합니다. 이후 std::next_permutation 함수를 거치며 감소하는 요소에서 swap이 일어나므로, 그 다음 조합은 {1, 1, 0, 1, 0} 이 되는 식입니다. 이렇게 {0, 0, 1, 1, 1} 까지 탐색을 하게 됩니다.

방법2는 불필요한 함수 호출을 줄일 수 있고, lexicographical order 의 사전식 정렬을 하기 때문에 모든 경우의 수를 중복없이 방문한다는 장점이 있습니다.

좀 더 std::next_permutation 의 동작 로직에 대해 알아보기 위해 검색을 해보았습니다.

https://stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation
std::next_permutation 의 동작 로직 설명

while (true)
{
	It j = i;
	--i;

	if (*i < *j)
	{
		It k = end;

		while (!(*i < *--k))
				/* pass */;

		iter_swap(i, k);
		reverse(j, end);
		return true;
	}

	if (i == begin)
	{
		reverse(begin, end);
		return false;
	}
}