[백준]#1039 교환

문제

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

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

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

입력

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제에 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 K번 할 수 없으면 -1을 출력한다.

예제 입력 1

16375 1

예제 출력 1

76315

예제 입력 2

132 3

예제 출력 2

312

풀이

이 문제는 bfs(너비 우선 탐색) 알고리즘을 이용해서 풀 수 있었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int max = -1;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        bfs(input[0], Integer.parseInt(input[1]));

        System.out.println(max);
    }

    public static void bfs(String start, int cnt_max) {
        Queue<Pair> queue = new LinkedList<>();
        boolean[][] visited = new boolean[1000001][11];       //중복 체크를 위한 boolean 배열
        visited[Integer.parseInt(start)][0] = true;
        queue.add(new Pair(start, 0));
        StringBuilder sb;

        while(!queue.isEmpty()) {
            Pair temp = queue.poll();

            if(temp.cnt==cnt_max) {
                max = Math.max(max, Integer.parseInt(temp.str));
                continue;
            }

            for(int i=0; i<temp.str.length()-1; i++) {
                char c1 = temp.str.charAt(i);
                for(int j=i+1; j<temp.str.length(); j++) {
                    sb = new StringBuilder(temp.str);
                    char c2 = sb.charAt(j);

                    if(i==0 && c2=='0') continue;           //0이 맨 앞에 오는 경우 체크

                    sb.replace(i, i+1, Character.toString(c2));
                    sb.replace(j, j+1, Character.toString(c1));       //자리 교환

                    if(visited[Integer.parseInt(sb.toString())][temp.cnt+1]) continue;    //중복 
                    visited[Integer.parseInt(sb.toString())][temp.cnt+1] = true;
                    queue.add(new Pair(sb.toString(), temp.cnt+1));
                }
            }
        }
    }

    public static class Pair {
        String str;
        int cnt;

        public Pair(String str, int cnt) {
            this.str = str;
            this.cnt = cnt;
        }
    }
}