#백준_1039 교환 - Java 자바

#유형 : 그래프 탐색, BFS

#난이도 : 골드 3

# 맨 처음에는 어떻게 교환을 해야 가장 큰 수를 얻을 수 있을까 라는 생각으로 문제를 접근했다가 망했다. 이 문제에서 요구하는 것은 그것이 아니라 **K번의 위치 교환을 수행한 수 중에 가장 큰 수** 를 구하는 것이었다. 따라서 swap하여 중첩되지 않는 수를 큐에 넣으면서 구하는 문제였다. 이 때 중첩되지 않는 수는 어떻게 처리해야할까 생각하다가 1차원으로 처리하면 똑같은 수로 이루어진 4444, 5555 같은 숫자는 첫 번째 교환 후 연산을 할 수 없다. 따라서 2차원 boolean형 배열로 해결하였고, 또한 맨 앞자리가 0이 와선 안되므로 swap 할때 조건을 따져줘야 한다. 2차원 배열로 해도 되고, 아니면 1차원 배열을 사용하려면 큐 사이즈 만큼 반복문을 돌리면서 연산 한번을 수행할 때마다 배열을 초기화시켜주면 될 것같다.

 

필자의 경우에는 위치를 바꿔주기 위해 StringBulider 클래스를 사용하였는데 애초에 큐에 넣는 값을 String으로 넣어 toCharArray()를 통해 교환을 하는 것도 좋아보인다. 사람마다 방식은 다르니 참고만 하시길.

package bj;
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p1039 {
 
    static boolean visit[][] = new boolean[1000001][11];
    static int N,K;
    static String str;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        str = st.nextToken();
        N = Integer.parseInt(str);
        K = Integer.parseInt(st.nextToken());
        
        bfs();
        
    }
    private static void bfs() {
        // TODO Auto-generated method stub
        Queue<Point> queue = new LinkedList<Point>();
        queue.add(new Point(N, 0));
        visit[N][0] = true;
        while(!queue.isEmpty()) {
            
            if(queue.peek().y == K)
                break;
            
            Point po = queue.poll();
            for(int i=0; i<str.length()-1; i++) {
                for(int j=i+1; j<str.length(); j++) {
                    int next = solve(po.x, i, j);
                    if(next != -1 && !visit[next][po.y+1]) {
                        visit[next][po.y+1] = true;
                        queue.add(new Point(next, po.y+1));
                    }
                }
            }
        }
        int result = -1;
        while(!queue.isEmpty()) {
            Point po = queue.poll();
//            System.out.println(po.x);
            if(result < po.x)
                result = po.x;
        }
        
        System.out.println(result);
        
        
    }
    private static int solve(int x, int i, int j) {
        // TODO Auto-generated method stub
        StringBuilder sb = new StringBuilder();
        sb.append(x);
        if(i==0 && sb.charAt(j)=='0')
            return -1;
        
        char tmp = sb.charAt(i);
        sb.setCharAt(i, sb.charAt(j));
        sb.setCharAt(j, tmp);
        return Integer.parseInt(sb.toString());
    }
}