백준 - 1039번 : 교환 (C++)

풀이 방법 : DFS

무식하게 풀고 맞긴 했는데, 풀고 나서 분류를 보니 너비 우선 탐색이라고 나와있긴 하더라 깊이 우선 탐색으로 풀면 중복 탐색 막는 과정이 번거로워져서 이렇게 분류된건가 싶다.

그냥 재귀함수에서 이중 for문 돌리면서 넘겨받은 문자열의 각 문자들을 swap해가면서 swap 횟수가 K에 도달한 녀석을 저장하고 최종적으로 K번 swap한 결과물들 중 최댓값을 출력해주는 방식으로 구현했다.

vector에다 set 컨테이너를 넣어두고 각각의 swap 횟수 별로 이미 탐색한 문자열이 있으면 탐색 대상에서 제외했다.

#include <iostream>
#include <string>
#include <vector>
#include <set>

using namespace std;

void Swap(string Current,int Length, int Cnt, int K,
vector<string>& vecString, vector<set<string>>& vecSet)
{
	if (Cnt == K)
	{
		vecString.push_back(Current);
		return;
	}

	for (int i = 0; i < Length; ++i)
	{
		for (int j = i; j < Length; ++j)
		{
			if (i == j)
				continue;

			char Temp;

			Temp = Current[i];
			Current[i] = Current[j];
			Current[j] = Temp;

			auto iter = vecSet[Cnt].find(Current);
			auto iterEnd = vecSet[Cnt].end();

			if (iter == iterEnd)
			{
				if (Current[0] != '0')
				{
					vecSet[Cnt].insert(Current);
					Swap(Current, Length, Cnt + 1, K, vecString, vecSet);
				}
			}

			
			Temp = Current[i];
			Current[i] = Current[j];
			Current[j] = Temp;
		}
	}
	
}

int main()
{
	string N;
	int K;

	cin >> N >> K;

	int Length = N.length();

	vector<string> vecString;
	vector<set<string>> vecSet;
	vecSet.resize(K);

	Swap(N, Length, 0, K, vecString, vecSet);
	
	int Size = vecString.size();

	string Max = "-1";

	for (int i = 0; i < Size; ++i)
	{
		if (stoi(Max) < stoi(vecString[i]))
			Max = vecString[i];
	}

	cout << Max << '\n';
}

중복 탐색을 막을 때 같은 숫자더라도 swap 횟수가 다르면 다른 결과라는 것을 빨리 캐치해야 편하게 풀 수 있는 문제인 거 같다.