1039_교환

사용 알고리즘: bfs

사용 언어: java

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_bj_1039_교환 {
    static int n, k;
    static int ans = -1; //안 되면 -1 출력
    static boolean[][] visited;
    static int len;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken()); // 주어진 정수
        k = Integer.parseInt(st.nextToken()); // 연산 횟수
        visited = new boolean[k+1][1000001]; // k번째 연산에서 만들어진 수 : [i][1] => n은 1000000보다 작거나 같은 자연수라고 문제에서 주어짐
        len = String.valueOf(n).length();

        bfs_1039();

        System.out.println(ans);
    }

    private static void bfs_1039() {
        Queue<Nums> q = new ArrayDeque<>();
        q.add(new Nums(n, 0)); //초기 수 n과 연산 횟수 0번
        visited[0][n] = true;

        while (!q.isEmpty()) {
            Nums curNum = q.poll();

            // k번 연산을 했다면 ans 갱신하고, 다음 연산
            if (curNum.k >= k) {
                ans = Math.max(ans, curNum.num);
                continue;
            }

            for (int i = 0; i < len-1; i++) {
                for (int j = i+1; j < len; j++) {
                    int nxt = swap_1039(curNum.num, i, j);
                    if(nxt != -1) { //연산 결과값이 허용 가능한 수라면
                        if (!visited[curNum.k+1][nxt]) {
                            visited[curNum.k+1][nxt] = true;
                            q.add(new Nums(nxt, curNum.k+1));
                        }
                    }
                }
            }
        }
    }

    private static int swap_1039(int num, int i, int j) {
//        System.out.println("num: " + num);
        char[] num2 = String.valueOf(num).toCharArray();

        char tmp = num2[i];
        num2[i] = num2[j];
        num2[j] = tmp;

        if(num2[0] == '0') return -1;
        return Integer.parseInt(new String(num2));
    }
}

class Nums {
    int num;
    int k;

    public Nums(int num, int k) {
        this.num = num;
        this.k = k;
    }
}

 

이해를 해버렸다 이거야

클래스도 써봤다 이거야