[백준 1039] 교환

방문배열 써야된다... 우선순위 큐 조건 잘 주자..

 

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

1039번: 교환

#include <iostream>
#include <string>
#include <queue>
std::string s;
int K;
int visited[1000000 + 2][10 + 2];	// 10번까지 바꿀 수 있다. 

struct _qt
{
	std::string num;
	int change;
};

struct COMP
{
	bool operator() (_qt &a, _qt &b)
	{
		if (a.change == b.change) return a.num < b.num;
		return a.change > b.change;
	}

};

std::priority_queue<_qt, std::vector<_qt>, COMP> PQ;

void input()
{
	std::cin >> s >> K;
	PQ.push({ s, 0 });
	visited[stoi(s)][0] = 1;
}


std::string BFS()
{
	while (!PQ.empty()) {
		_qt data = PQ.top();
		PQ.pop();

		if (data.change == K) return data.num;

		int max = 0;
		for (int i = 0; i < data.num.size() - 1; i++) {
			for (int j = i + 1; j < data.num.size(); j++) {
				std::string nnum = data.num;
				int nchange = data.change + 1;

				char tmp = nnum[i];
				nnum[i] = nnum[j];
				nnum[j] = tmp;
				if (nnum[0] == '0') continue;
				if (visited[stoi(nnum)][nchange]) continue;
				//std::cout << nnum << " " << data.change << "\n";
				PQ.push({ nnum, nchange });
				visited[stoi(nnum)][nchange] = 1;
			}
		}

	}
	return "-1";
}



int main()
{
	input();
	std::cout << BFS() << "\n";
	return 0;
}

우선순위 큐에 조건 거지 같이 주고 외않되 외않되 하고있었다.

1000,000자리라고 하더라도 자리수 교환으로 치면 연산이 얼마 안돼서 for 루프 두 개로 나올 수 있는 모든 수 만들어보고, 그것을 우선순위 큐에 집어넣어야겠다고 생각했다. 

 

근데 여기서 간과한 부분은 

1. PQ에 들어있는 원소 중 무작정 가장 큰 수를 뽑아내는 것이 아니라, 교환 횟수가 K에 가까운 숫자 중 큰 수를 뽑아야 한다. 그래서 COMP 구조체에 조건이 2개 들어가 있는 것이다... 

나는 이걸 놓치고 그냥 return a.num < b.num 만 해줌... 틀림 .. 

2. 방문배열 안쓰면 메모리 초과난다. 

스트링이라서 그런가... ? 교환횟수가 nchange일때 만들어진 숫자 nnum에 대하여 만약 기존에 해당 숫자가 만들어진 경험이 있는 경우(visited[stoi(nnum)][nchange] != 0) 스루해주어야 한다.