[백준 1039] 교환(Java)

문제 링크 : https://www.acmicpc.net/problem/1039

이 문제는 bfs를 통해 풀 수 있습니다. 처음에는 백트래킹으로 생각해서 접근했더니 계속 메모리 초과가 났는데 다시 생각해보니 탐색을 다시 처음으로 돌아와서 진행할 필요 없이 쭉 변경하면서 최대값을 탐색해도 모든 값을 탐색할 수 있습니다.

주의할 점은 문제에서 조건에 만족하지 않는 경우를 잘 골라내야 합니다. 우선 변경 시 맨 앞의 수가 0이면 안되므로 변경할 인덱스 중 0이 존재하고, 변경되는 수가 0일 경우는 bfs 큐에 추가하면 안됩니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

class Pair{
    int num;
    int cnt;

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

public class Main{
    static int N,K;
    static int res = -1;

    static void bfs(){
        boolean[][] check = new boolean[1000001][K+1];
        check[N][0] = true;
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(N,0));

        while(!q.isEmpty()){
            Pair curr = q.poll();

            // 바꾼 횟수를 다 소모했을 경우 최대값 여부를 체크
            if(curr.cnt==K){
                if(res<curr.num) res = curr.num;
                continue;
            }

            // i < j 이므로 반복문을 아래와 같이 설정
            int l = Integer.toString(curr.num).length();
            for(int i=0;i<l-1;i++){
                for(int j=i+1;j<l;j++){
                    int new_num = changed_num(curr.num, i,j);

                    if(
                            // 바꾼 수의 맨 앞이 0일 경우
                            new_num != -1 &&

                            // 아직 확인하지 않은 수인 경우
                            !check[new_num][curr.cnt+1]
                    ){
                        // 체크 후 큐에 추가
                        check[new_num][curr.cnt+1] = true;
                        q.add(new Pair(new_num, curr.cnt+1));
                    }
                }
            }
        }
    }

    static int changed_num(int num, int idx_first, int idx_second){
        String str = Integer.toString(num);

        // 바꾸려는 인덱스 중 가장 앞의 인덱스가 0이고(맨 앞자리) 뒤의 인덱스가 가리키는 숫자가 0일 경우
        // 맨 앞으로 0을 넣는 경우이므로 불가능
        if(str.charAt(idx_second)=='0' && idx_first==0) return -1;

        char first = str.charAt(idx_first);
        char second = str.charAt(idx_second);

        // 두 수를 변환
        StringBuilder sb = new StringBuilder(str);
        sb.setCharAt(idx_first,second);
        sb.setCharAt(idx_second,first);

        return Integer.parseInt(String.valueOf(sb));
    }

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

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        bfs();
        System.out.println(res);
    }
}