[백준] 1039 - 교환(Java)

문제 파악

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

풀이

문제는 주어진 수 N의 자릿수 중 두 자리를 최대 K번까지 바꾸어
가장 큰 수를 만드는 문제다.

단, 교환 결과의 수가 0으로 시작하면 안 되며, 숫자 자리수가 1개인 경우 교환 자체가 불가능하다.

최대 depth가 K인 트리를 탐색하는 문제라고 판단했다.

BFS로 탐색하기로 결정했으며,
동일한 depth(교환 횟수)의 문자열의 중복을 제거하는 것이 핵심이라고 생각했다.
이 문제에서는 중복 제거를 위해 Map 자료구조를 활용했다.

사용한 Map은

• Key : 교환 횟수 [0, K]
• Value : 해당 횟수에서 만들 수 있는 수들을 저장하는 집합 (Set)

로 구성된다.

BFS 탐색을 위해 큐를 순회하며 다음 depth에 위치를 바꾼 문자열을 삽입한다.
이 때 Map을 활용해여 동일 depth(key)에 문자열이 있는지 체크하고, 문자열이 존재한다면 큐에 삽입하지 않는다.

추가로 신경 쓸 부분은 '첫번째 자리수가 0이 되면 안된다'이다.
이를 구현하기 위해 문자열 변환 시 조건을 추가해주도록 하자.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);
        int len = String.valueOf(N).length();
        
        HashMap<Integer, Set<String>> map = new HashMap<>();
        for (int i = 0; i <= K; i++) {
            map.put(i, new HashSet<>());
        }
        
        int answer = -1;
        Queue<Status> queue = new LinkedList<>();
        queue.offer(new Status(String.valueOf(N), 0));
        
        while (!queue.isEmpty()) {
            Status latest = queue.poll();
            String currentStr = latest.current;
            int currentCount = latest.count;
            
            if (currentCount == K) {
                answer = Math.max(answer, Integer.parseInt(currentStr));
                continue;
            }
            
            for (int i = 0; i < len; i++) {
                char temp = currentStr.charAt(i);
                for (int j = i + 1; j < len; j++) {
                    // 첫 자리수가 0이 되는 경우 스킵
                    if (i == 0 && currentStr.charAt(j) == '0') {
                        continue;
                    }
                    char[] toArr = currentStr.toCharArray();
                    toArr[i] = toArr[j];
                    toArr[j] = temp;
                    Set<String> nextSet = map.get(currentCount + 1);
                    String nextStr = String.valueOf(toArr);
                    if (!nextSet.contains(nextStr)) {
                        queue.offer(new Status(nextStr, currentCount + 1));
                        nextSet.add(nextStr);
                    }
                }
            }
        }
        System.out.println(answer);
    }

    private static class Status {
        String current;
        int count;

        public Status(String current, int count) {
            this.current = current;
            this.count = count;
        }
    }
}