백준 1039: 교환

문제 요약

0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.

1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS

문제 풀이

BFS로 탐색하여 풀면 되는데, 321->312->321처럼 앞서 방문했던 값을 다시 방문할 수 있다.

즉, 하나의 레벨에서 방문 할 때마다 계속해서 visited배열을 초기화 주어야 한다.

그렇게 k번 반복하여 큐에 남은 값들 중 큰 값을 출력하면 된다.

여기서 나는 두가지 해법을 생각하였다. 첫번째는 입력을 string으로 받는 것이고, 두번째는 int로 받는 방법이다. 문제를 잘못 이해하여 여러가지 방법들을 시도해보았는데, 결국 string과 set으로도 풀리고, int와 bool[]로도 풀렸다.

우선, 100 1을 입력으로 주어도 출력은 100이다. 10의 자리 0과 1의 자리 0을 교환하면 되기 때문이다.

이 반례를 찾지 못했었는데, 그쪽 if문을 고쳐주니 바로 풀렸다.

string의 경우에는 i가 j보다 자리수가 높고, int의 경우에는 j가 i보다 자리수가 높게 코딩하였다. 각 자리수 계산에도 유의하여야 한다.

풀이 코드

• string으로 푼 예시

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>

using namespace std;

queue<string> q;
set<string> visited;

int main()
{
	string in, next;
	int k, MAX = -1, qsize, val;

	cin >> in >> k;
	q.push(in);
	while (k > 0) {
		qsize = q.size();
		k--;
		if (!qsize) break;
		visited = set<string>();
		while (qsize--) {
			in = q.front();
			q.pop();
			for (int i = 0; i < in.length() - 1; i++) {
				for (int j = i + 1; j < in.length(); j++) {
					if (i == 0 && in[j] == '0') continue;
					next = in;
					swap(next[i], next[j]);
					if (visited.find(next) == visited.end()) {
						visited.insert(next);
						q.push(next);
					}
				}
			}
		}
	}
	while (!q.empty()) {
		val = stoi(q.front());

		if (MAX < val) MAX = val;
		q.pop();
	}
	cout << MAX;
	return 0;
}

• int로 푼 예시

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;

queue<int> q;
bool visited[1000001];

int main()
{
	int in, next, length, pi, pj, vali, valj;
	int k, MAX = -1, qsize, val;

	cin >> in >> k;
	for (int i = 10, j = 1;; i *= 10, j++) {
		if (in / i == 0) {
			length = j;
			break;
		}
	}
	q.push(in);
	while (k > 0) {
		qsize = q.size();
		k--;
		if (!qsize) break;
		fill(visited, visited + 1000001, false);
		while (qsize--) {
			in = q.front();
			q.pop();
			pi = 1;
			for (int i = 0; i < length; i++) {
				pj = pi * 10;
				for (int j = i + 1; j < length; j++) {
					vali = (in / pi) % 10;
					valj = (in / pj) % 10;
					if (vali == 0 && j == length - 1) continue;
					next = in;
					next -= vali * pi;
					next += valj * pi;
					next -= valj * pj;
					next += vali * pj;
					if (!visited[next]) {
						visited[next] = true;
						q.push(next);
					}
					pj *= 10;
				}
				pi *= 10;
			}
		}
	}
	while (!q.empty()) {
		val = q.front();
		if (MAX < val) MAX = val;
		q.pop();
	}
	cout << MAX;
	return 0;
}