[백준]1039 - 교환 문제 풀이(자바,Java)

문제

1039번: 교환

들어가며

완전 탐색 기법으로 문제를 풀었습니다.

다만, dfs를 처음 이용했는데 메모리 초과로 계속해서 못풀었습니다.

겨우 답지보고 bfs 접근을 해야 함을 깨달았습니다.

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class 백준1039_교환 {
    static int k;
    static String originalNum;
    static int result = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        originalNum = st.nextToken();
        k = Integer.parseInt(st.nextToken());

        search();
        if (result == Integer.MIN_VALUE){
            System.out.println(-1);
            return;
        }
        System.out.println(result);
    }

    private static void search() {
        Queue<Point> queue = new ArrayDeque<>();
        HashSet<String>[] visited;
        visited = new HashSet[k + 1];
        for (int d = 0; d <= k; d++) {
            visited[d] = new HashSet<>();
        }
        queue.add(new Point(originalNum,0));
        while (!queue.isEmpty()) {
            Point current = queue.poll();

            if (current.depth == k) {
                result = Math.max(result, Integer.parseInt(current.data));
                continue;
            }
            char[] arr = current.data.toCharArray();
            for (int i = 0; i < arr.length; i++) {
                for (int j = i+1; j < arr.length; j++) {
                    if (arr[j] == '0' && i == 0) continue; // leading zero check

                    // swap
                    char[] copy = current.data.toCharArray();
                    char temp = copy[i];
                    copy[i] = copy[j];
                    copy[j] = temp;

                    String next = new String(copy);
                    if (!visited[current.depth+1].contains(next)) {
                        visited[current.depth+1].add(next);
                        queue.add(new Point(next, current.depth+1));
                    }
                }
            }
        }
    }
    private static class Point{
        String data;
        int depth;

        public Point(String data, int depth) {
            this.data = data;
            this.depth = depth;
        }
    }
}

 

풀이

단순 무식한 방법인 bfs를 사용했습니다.

여기서 dfs가 안되는 이유는 메모리 초과 문제도 있지만, recursion이 많이 발생하기 때문입니다.

그래서 stack으로 하시거나 더 편한 bfs로 접근하는 것이 풀기 좋습니다.

private static void search() {
    Queue<Point> queue = new ArrayDeque<>();
    HashSet<String>[] visited;
    visited = new HashSet[k + 1];
    for (int d = 0; d <= k; d++) {
        visited[d] = new HashSet<>();
    }
    queue.add(new Point(originalNum,0));
    while (!queue.isEmpty()) {
        Point current = queue.poll();

        if (current.depth == k) {
            result = Math.max(result, Integer.parseInt(current.data));
            continue;
        }
        char[] arr = current.data.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                if (arr[j] == '0' && i == 0) continue; // leading zero check

                // swap
                char[] copy = current.data.toCharArray();
                char temp = copy[i];
                copy[i] = copy[j];
                copy[j] = temp;

                String next = new String(copy);
                if (!visited[current.depth+1].contains(next)) {
                    visited[current.depth+1].add(next);
                    queue.add(new Point(next, current.depth+1));
                }
            }
        }
    }
}
private static class Point{
    String data;
    int depth;

    public Point(String data, int depth) {
        this.data = data;
        this.depth = depth;
    }
}

여기서 k를 depth로 판단합니다.

한 번 swap 하게 되면 depth + 1를 해서 층을 늘려가는 방식입니다.

이렇게 했을 때, visited 처리가 애매해집니다.

하지만, 각 depth마다 만들어진 숫자인 data는 이전 depth에서 똑같은 숫자이더라도 다르게 취급해야 합니다.

(이 문제에선 어떤 자리를 swap 했는지가 중요함)

visited = new HashSet[k + 1];
for (int d = 0; d <= k; d++) {
    visited[d] = new HashSet<>();
}

visited를 2차원 배열로 처리해도 좋지만, 조금이라도 메모리를 아끼기 위해 HashSet 배열로 하여 같은 depth 내에서 똑같은 숫자에 도착했는지 안했는지 파악합니다.

if (current.depth == k) {
    result = Math.max(result, Integer.parseInt(current.data));
    continue;
}

이렇게 depth를 늘려가며 모든 경우의 수를 탐색하다가 k가 되면 result와 비교해서 최대값인지 아닌지를 저장합니다.

bfs는 끝나게 됩니다.

if (result == Integer.MIN_VALUE){
    System.out.println(-1);
    return;
}

마지막으로 연산이 안되는 경우엔 result가 변하지 않기 때문에 -1를 출력하는 걸 잊지맙시다.