[백준] 1039번 교환 (JAVA)

문제

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

1039번: 교환

 

설명

1 ≤ i < j ≤ M인 i와 j를 고른 뒤, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

1,000,000보다 작거나 같은 자연수인 N을 위의 연산을 K번 하는데 이는 바뀐 수도 1,000,000보다 작거나 같은 수라는 뜻이므로 1,000,000 크기의 visited 배열을 만들어 현재 depth에서 이미 만들어진 수는 또다시 연산을 수행하지 않도록 한다 그리고, queue를 만들어 처음에 N을 넣고 BFS을 수행한다.

int[] visited = new int[1000001];

Queue<Integer> queue = new LinkedList<>();
queue.offer(N);

bfs();

큐가 비어있지 않고 K가 0보다 클 때까지 연산을 하는데 연산 한 바퀴가 끝나면 K를 감소해가면서 종료조건을 만든다. 큐에서 하나씩 빼내서 i번째 자리의 수와 j번째 자리의 수를 swap 함수를 이용해 바꾼다. 바꾼 수에서 맨 앞 자리의 수가 0이면 연산을 더 이상 진행할 수 없기 때문에 큐에 넣지 않도록 한다. 그리고 이전에 방문한 적이 있던 수도 큐에 추가하지 않는다. 모든 과정이 끝나고 큐에 남아있는 수가 없다면 -1을 출력하고 있다면 그 중 가장 큰 수를 출력한다.

public static int swap(int now, int i, int j) {
    char[] list = String.valueOf(now).toCharArray();

    // 해당 자리의 숫자 교환
    char temp = list[i];
    list[i] = list[j];
    list[j] = temp;

    // 앞자리가 0이면 error
    if (list[0] == '0')
        return 0;

    return Integer.parseInt(new String(list));
}

static void bfs() {
    while (!queue.isEmpty() && K > 0) {
        int size = queue.size();
        for (int count = 0; count < size; count++) {
            int now = queue.poll();

            for (int i = 0; i < M - 1; i++) {
                for (int j = i + 1; j < M; j++) {
                    int next = swap(now, i, j);

                    // 앞자리가 0이거나 현재 depth에서 방문한 적이 있는 경우 queue에 추가하지 않음.
                    if (next != 0 && visited[next] != K) {
                        queue.offer(next);
                        visited[next] = K;
                    }
                }
            }
        }
        
        K--;
    }

    if (queue.isEmpty()) {
        System.out.println("-1");
    }
    else {
        int answer = 0;
        for (int num : queue) {
            answer = Math.max(num, answer);
        }
        System.out.println(answer);
    }
}

 

전체 코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N, K, M;
    static int[] visited;
    static Queue<Integer> queue;

    public static int swap(int now, int i, int j) {
        char[] list = String.valueOf(now).toCharArray();

        // 해당 자리의 숫자 교환
        char temp = list[i];
        list[i] = list[j];
        list[j] = temp;

        // 앞자리가 0이면 error
        if (list[0] == '0')
            return 0;

        return Integer.parseInt(new String(list));
    }

    static void bfs() {
        while (!queue.isEmpty() && K > 0) {
            int size = queue.size();
            for (int count = 0; count < size; count++) {
                int now = queue.poll();

                for (int i = 0; i < M - 1; i++) {
                    for (int j = i + 1; j < M; j++) {
                        int next = swap(now, i, j);

                        // 앞자리가 0이거나 현재 depth에서 방문한 적이 있는 경우 queue에 추가하지 않음.
                        if (next != 0 && visited[next] != K) {
                            queue.offer(next);
                            visited[next] = K;
                        }
                    }
                }
            }

            K--;
        }

        if (queue.isEmpty()) {
            System.out.println("-1");
        }
        else {
            int answer = 0;
            for (int num : queue) {
                answer = Math.max(num, answer);
            }
            System.out.println(answer);
        }
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = String.valueOf(N).length();
        K = Integer.parseInt(st.nextToken());

        visited = new int[1000001];

        queue = new LinkedList<>();
        queue.offer(N);

        bfs();
    }
}