[백준 1039] 교환(Java)

1. 문제

www.acmicpc.net/problem/1039

1039번: 교환

2. 풀이

• 풀이를 생각하는데 오랜 시간이 걸려 푸는 방법을 알아보니 BFS로 풀 수 있다하였다..
• 92%프로에서 계속 틀렸는데 이유는 10 1 을 입력받을 때 -1이 나오지 않았다.
• 예외처리하는데 어려웠다....

3. 코드

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


public class Main {
 
    static class Node{
        String num;
        int cnt;

        public Node(String num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }
    }
    static String n;
    static int k;
    static Queue<Node>que;
    static boolean[][]visited = new boolean[1000001][11];
    static int max = -1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = st.nextToken();
        k = Integer.parseInt(st.nextToken());
        bfs();
        System.out.println(max);
    }
    static void bfs(){
        que = new LinkedList<>();
        que.offer(new Node(n,0));
        while (!que.isEmpty()){
            Node top = que.poll();
            int len = top.num.length();
            if(top.cnt == k){
                max = Math.max(max,Integer.parseInt(top.num));
                continue;
            }
            for(int i =0; i<len-1; i++){
                for(int j =i+1; j<len; j++){
                    int next = sol(top.num, i,j);
                    if(next !=-1 && !visited[next][top.cnt+1]){
                        visited[next][top.cnt+1] = true;
                        que.offer(new Node(String.valueOf(next),top.cnt+1));
                    }
                }
            }
        }
    }
    static int sol(String a, int b, int c){
        char[]ch = a.toCharArray();
        if(b==0 && ch[c]=='0') {
            return -1;
        }
        char temp = ch[b];
        ch[b] = ch[c];
        ch[c] = temp;
        String str = String.valueOf(ch);
        return Integer.parseInt(str);
    }
}
//16375 1   76315

반응형