[JAVA] BOJ 백준 1039번 - 교환

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

DFS와 가지치기를 이용해 시간초과를 고려해야 하는 문제이다.

 

처음에 String으로 변환해 풀이를 할까 고민했는데, 값을 변경하고 다시 숫자로 변환하는 과정에서 속도가 비교적 느릴 것으로 판단했다. 따라서 나누기와 나머지 연산을 통해 변환할 위치의 숫자 두 개를 추출했고, 변환하려는 숫자가 첫 번째 자리(i = 0)임과 동시에 뒤에 나오는 숫자(rj)가 0일 경우는 불가능한 상황으로 continue; 문으로 처리했다.

 

그 후, visit 배열을 이용한 가지치기를 한다. visit[숫자][K번 변환]을 통해 이전에 k번의 변환에서 변환한 숫자를 방문한 적 없을 경우에만 dfs를 또다시 돌려주면 된다. 동일한 숫자 두 개를 여러 번 변환해야 할 경우도 존재하므로, 이차원 배열을 이용해야 한다.

public static void dfs(int num, int cnt) {
    if (cnt == K) {
        result = Math.max(result, num);
        return;
    }

    for (int i = 0; i < M; i++) {
        for (int j = i+1; j < M; j++) {
            int pi = (int) Math.pow(10, M - i - 1);
            int pj = (int) Math.pow(10, M - j - 1);
            int ri = (num / pi) % 10;
            int rj = (num / pj) % 10;

            int nextNum = num;
            nextNum -= pi * ri + pj * rj;
            nextNum += pi * rj + pj * ri;

            if (nextNum == 0 || (i == 0 && rj == 0)) continue;
            if (visit[nextNum][cnt + 1]) continue;

            visit[nextNum][cnt + 1] = true;
            dfs(nextNum, cnt + 1);
        }
    }
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B1039.java

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

class Main {
    static int N, M, K;
    static boolean[][] visit;
    static int result;

    public static void main (String[] args) throws IOException {
        input();
        solution();
        output();
    }

    public static void solution() {
        visit[N][0] = true;
        dfs(N, 0);
    }

    public static void dfs(int num, int cnt) {
        if (cnt == K) {
            result = Math.max(result, num);
            return;
        }

        for (int i = 0; i < M; i++) {
            for (int j = i+1; j < M; j++) {
                int pi = (int) Math.pow(10, M - i - 1);
                int pj = (int) Math.pow(10, M - j - 1);
                int ri = (num / pi) % 10;
                int rj = (num / pj) % 10;

                int nextNum = num;
                nextNum -= pi * ri + pj * rj;
                nextNum += pi * rj + pj * ri;

                if (nextNum == 0 || (i == 0 && rj == 0)) continue;
                if (visit[nextNum][cnt + 1]) continue;

                visit[nextNum][cnt + 1] = true;
                dfs(nextNum, cnt + 1);
            }
        }
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void input() 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());
        visit = new boolean[1000001][K+1];
        result = -1;

        br.close();
    }
}

---

4. 결과 및 회고

처음에 바로 어떻게 풀어야 할지 알았는데, visit[숫자][k번 변환]으로 가지치기해야 하는 것은 나중에 생각해냈다. 처음 풀 때 머릿속에서 충분한 시뮬레이션을 돌려봐야겠다.