백준 : 1039 JAVA

https://www.acmicpc.net/problem/1039

1039번: 교환

 

처음 문제를 접했을 때는 완전탐색으로 2개를 짝지어 교환하는 경우의수 7! 카운트가 최대 10개 

완탐을 했더니  메모리초과가 발생하였다 아마 (7!) ^ 10 의 경우의를 탐색해거 그런것 같다.

따라서 BFS문제로 접근하였다. 자리를 바꾼다는것은  visit[num][cnt] 로 지정해서 cnt 인 카운터로 num을 방문 했는가 안했는가를 boolean형으로 관리하고 넢이우선순위 연산을 진행한다. 이대 중간에 '0'이 맨앞에 오는 경우도 갈수가 없는걸 처리하면 정답이나온다.

핵심은 어떤 경로로 두번 교환해서 num 값이 나왓다면 다른경로로와서 두번교환해서 num값이 나온것은 한번더 방문할  필요가 없다는 것이다. 이후에 가는 탐색이 똑같기 때문이다. 

package day0307;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
import day0307.B1039.Pair;
 
public class B1039 {
    static char A[];
    static int K;
    static int Answer =-1;
    static int size;
    static int[][] dp;
    static class Pair{
        int num;
        int cnt;
        public Pair(int num, int cnt) {
            super();
            this.num = num;
            this.cnt = cnt;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        A = st.nextToken().toCharArray();
        K = Integer.parseInt(st.nextToken());
        boolean visit[][] = new boolean[1000001][11];
        size = A.length;
        int num = Integer.parseInt(String.valueOf(A));
        Queue<Pair> q = new LinkedList<>();
 
        visit[num][0] = true;
        q.add(new Pair(num, 0));
        
        while(!q.isEmpty()) {
            Pair tmp = q.poll();
            char[] c = String.valueOf(tmp.num).toCharArray();
            
            if(tmp.cnt == K) {
                Answer = Math.max(Answer, tmp.num);
                continue;
            }
            
            for(int i=0;i<size-1;i++) {
                for(int j=i+1;j<size;j++) {
                    char buf = c[i];
                    c[i] = c[j];
                    c[j] = buf;
                    num = Integer.parseInt(String.valueOf(c));
                    
                    if(c[0]=='0' || visit[num][tmp.cnt+1]) {
                        buf = c[i];
                        c[i] = c[j];
                        c[j] = buf;
                        continue;
                    }
                    
                    visit[num][tmp.cnt+1] = true;
                    q.add(new Pair(num,tmp.cnt+1));
                    buf = c[i];
                    c[i] = c[j];
                    c[j] = buf;
                }
            }
        }
        
        
        System.out.println(Answer);
    }
 
}