[백준] 1039. 교환

문제 링크

[백준] 1039. 교환

풀이 과정

완전 탐색을 통해 문제를 해결하려고 한다면, $({}_7 \mathrm{ C }_2)^{10}≒ 10^{13}$ 만큼의 시간이 걸립니다. 자릿수 교환을 통해 만들어지는 새로운 수들로 bfs 탐색 을 해, 방문 처리된 숫자는 건너 뛰어 시간을 단축시킬 수 있습니다.

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N, K;
    static boolean[][] visit = new boolean[1000001][11];
    static int answer = -1;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        K = sc.nextInt();

        Queue<Pair> queue = new LinkedList<>();
        visit[N][0] = true;
        queue.add(new Pair(N, 0));

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

            if (now.cnt == K) {
                answer = Math.max(answer, now.num);
                continue;
            }

            int length = String.valueOf(N).length();

            for (int i = 0; i < length - 1; i++) {
                for (int j = i + 1; j < length; j++) {
                    char[] swapped = swap(now.num, i, j);
                    int num = Integer.parseInt(String.valueOf(swapped));

                    if (swapped[0] == '0' || visit[num][now.cnt + 1])
                        continue;

                    visit[num][now.cnt + 1] = true;
                    queue.add(new Pair(num, now.cnt + 1));
                }
            }
        }

        System.out.println(answer);
    }

    private static class Pair {
        int num, cnt;

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

    private static char[] swap(int num, int i, int j) {
        StringBuilder sb = new StringBuilder(String.valueOf(num));

        char tmp = sb.charAt(i);
        sb.setCharAt(i, sb.charAt(j));
        sb.setCharAt(j, tmp);

        return sb.toString().toCharArray();
    }
}