[JAVA] BOJ 백준 1039번 - 교환

목차

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

---

1. 문제

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

---

2. 내가 푼 방법

DFS 알고리즘을 이용해 푼 문제이다. 하지만 우리가 완전탐색을 진행할 때 중요한 부분이 이미 방문한 노드(숫자) 일 경우에는 다시 방문하지 않는 가지치기가 중요하다. 따라서 이차원 배열을 통해 방문한 숫자인지 확인해주는 것이 필요했다.

 

또한 맨 앞자리가 0이 되면 안 되는 것이었으므로 숫자의 길이가 달라질 경우에는 바로 리턴을 할 수 있도록 해주었다.

public static void dfs(int num, int cnt) {
    if (String.valueOf(num).length() != String.valueOf(N).length()) return;
    if (visit[num][cnt]) return;
    if (cnt == K) {
        result = Math.max(result, num);
        return;
    }

    visit[num][cnt] = true;

    for (int i = 0; i < String.valueOf(N).length(); i++) {
        for (int j = i+1; j < String.valueOf(N).length(); j++) {
            // i와 j 위치 바꾸기
            StringBuilder sb = new StringBuilder(String.valueOf(num));
            sb.setCharAt(i, String.valueOf(num).charAt(j));
            sb.setCharAt(j, String.valueOf(num).charAt(i));

            dfs(Integer.parseInt(sb.toString()), cnt+1);
        }
    }
}

 

---

3. 자바 코드

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

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

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

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

    public static void solution() {
        dfs(N, 0);
    }

    public static void dfs(int num, int cnt) {
        if (String.valueOf(num).length() != String.valueOf(N).length()) return;
        if (visit[num][cnt]) return;
        if (cnt == K) {
            result = Math.max(result, num);
            return;
        }

        visit[num][cnt] = true;

        for (int i = 0; i < String.valueOf(N).length(); i++) {
            for (int j = i+1; j < String.valueOf(N).length(); j++) {
                // i와 j 위치 바꾸기
                StringBuilder sb = new StringBuilder(String.valueOf(num));
                sb.setCharAt(i, String.valueOf(num).charAt(j));
                sb.setCharAt(j, String.valueOf(num).charAt(i));

                dfs(Integer.parseInt(sb.toString()), cnt+1);
            }
        }
    }

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

        bw.write(result+"");

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

    public static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        result = -1;

        visit = new boolean[1000001][K+1];

        br.close();
    }
}

 

---

4. 결과 및 회고

숫자가 해당 뎁스에 방문한 적이 있는지 확인하는 이차원 배열인 visit의 역할이 중요했다. 처음에 숫자를 잘못보고 1000001이 아닌 10000000을 선언해 줬더니 메모리초과가 났는데, 실수를 줄여보도록 해보장.