[백준]1039_교환

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

Solved

✔ 브루트포스

✔ BFS + (DP 얹은 사람도 있더라)

✔ 예외처리를 잘 하자
-- 1. 1000000 → 그대로 정답
-- 2. 1~9, 10, 20, 30, ..., 90 → 교환이 안됨(-1)

✔ 브루트포스만 한다면.. (6C2)^10 이므로 시간초과

✔ 한 번 갔는데 또 두 번 해당 숫자를 보는 것은 또 볼 필요가 없기 때문에.. 어딘가에 담아서 이 숫자가 이전에 확인했던 적이 있는지 구분하는 과정이 필요해서 BFS

✔ BFS라 하면 보드판에서 이동하는 문제만 떠오르기 쉬운데 그 생각을 고치는 계기가 되었다. '[백준]1103_게임'처럼 중복되는 연산을 걸러주는, 메모지에이션이 필요한 문제같다. 나의 풀이에선 메모지에이션 대신 연산 결과들을 다 안고 갔다.

✔ 1. 완전탐색을 고려한다. 2. 시간초과가 날 것같으면 중복 연산을 줄일 수 있는 방법을 고민한다. (dp, bfs, ...) 의 자세를 갖추자!!

using namespace std;
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#define MAX 1000001

int n, k;
bool visit[MAX];

int main() {
	cin >> n >> k;
	//예외가 되는 것들은 바로 처리
	// 1000000 ==> 그대로 답
	// 1~9 ==> 교환이 안됨 ==> -1
	// 10, 20, .., 90 ==> 교환이 안됨 ==> -1
	if (1 <= n && n <= 9) {
		cout << "-1\n";
		return 0;
	}
	else if (n == 10 || n == 20 || n == 30 || n == 40 || n == 50 || n == 60 ||
		n == 70 || n == 80 || n == 90) {
		cout << "-1\n";
		return 0;
	}
	//todo - 브루트포스
	//숫자를 직접 교환하는 로직
	//교환해서 단계별로 탐색해가는 로직
	//그리고 답 구하면 됨
	queue<int> q;
	q.push(n);

	for (int i = 0; i < k; i++) {
		//교환하고 탐색 ==> queue
		int sz = q.size();
		memset(visit, false, sizeof(visit));
		for (int j = 0; j < sz; j++) {
			int num = q.front();
			string num_s = to_string(num);
			q.pop();
			//교환 진행
			for (int a = 0; a < num_s.size(); a++) {
				for (int b = a + 1; b < num_s.size(); b++) {
					//교환 결과를 queue에 넣기
					//q에 중복해서 값이 들어갈 수 있기 때문에 중복체크
					//중복체크 방법 1. visit 배열을 이용
					//중복체크 방법 2. map을 이용
					if (a == 0 && num_s[b] == '0') continue;
					int x = conv(num_s, a, b);
					if (visit[x] == 0) {
						visit[x] = true;
						q.push(x);
					}
				}
			}

		}
	}
	//k번을 돌렸기 때문에 q에 남아 있는 것들은 k번을 수행하고 남은 숫자들이고
	//q에 남은 것들 중 가장 큰 값이 답이다.
	int answer = q.front();
	int sz = q.size();
	while (sz--) {
		answer = max(answer, q.front());
		q.pop();
	}
	cout << answer << '\n';
	return 0;
}