[Java] 백준 9019 - DSLR

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

9019번: DSLR

최초 코드

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

class Main {
    private static int idx = 0;
    private static int[] minArr;
    private static String[] cmds;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        minArr = new int[T];
        cmds = new String[T];
        Arrays.fill(minArr, Integer.MAX_VALUE);

        for (int i = 0; i < T; i++) {
            String[] input = br.readLine().split(" ");
            String A = input[0];
            String B = input[1];

            dfs(fillZero(new StringBuilder(A)), new StringBuilder(), fillZero(new StringBuilder(B)).toString(), 0);
            idx++;
        }

        Arrays.stream(cmds).forEach(System.out::println);
    }

    private static void dfs(StringBuilder current, StringBuilder cmd, String answer, int depth) {
        if (depth > 5 || depth >= minArr[idx]) {
            return;
        }

        if (current.toString().equals(answer)) {
            if (cmd.length() < minArr[idx]) {
                minArr[idx] = cmd.length();
                cmds[idx] = cmd.toString();
            }
            return;
        }

        for (int i = 0; i < 4; i++) {
            //명령어 적용
            StringBuilder[] beforeAndAfter = calc(current, i);
            dfs(beforeAndAfter[1], cmd.append(beforeAndAfter[2].toString()), answer, depth + 1);
            cmd.deleteCharAt(cmd.length()-1);
        }
    }

    private static StringBuilder[] calc(StringBuilder current, int flag) {
        StringBuilder res;
        String executed = "";
        int parsed = 0;
        char[] d = null;

        if (flag == 0 || flag == 1) {
            parsed = Integer.parseInt(current.toString());
        } else {
            d = new char[4];
            d[0] = current.charAt(0);
            d[1] = current.charAt(1);
            d[2] = current.charAt(2);
            d[3] = current.charAt(3);
        }

        //D
        if (flag == 0) {
            parsed *= 2;
            if (parsed > 9999) {
                parsed %= 10000;
            }
            res = new StringBuilder(String.valueOf(parsed));
            executed = "D";
        }
        //S
        else if (flag == 1) {
            parsed -= 1;
            res = parsed < 0 ? new StringBuilder(String.valueOf(9999)) : new StringBuilder(String.valueOf(parsed));
            executed = "S";
        }
        //L
        else if (flag == 2) {
            res = new StringBuilder().append(d[1]).append(d[2]).append(d[3]).append(d[0]);
            executed = "L";
        }
        //R
        else {
            res = new StringBuilder().append(d[3]).append(d[0]).append(d[1]).append(d[2]);
            executed = "R";
        }

        return new StringBuilder[]{current, fillZero(res), new StringBuilder(executed)};
    }

    private static StringBuilder fillZero(StringBuilder sb) {
        if(sb.length()==4){
            return sb;
        }

        if (sb.length() == 1) {
            for (int i = 0; i < 3; i++) {
                sb.insert(0, '0');
            }
            return sb;
        }
        if (sb.length() == 2) {
            for (int i = 0; i < 2; i++) {
                sb.insert(0, '0');
            }
            return sb;
        }
        sb.insert(0, '0');
        return sb;
    }

}

 

DFS나 BFS 둘 중 아무거나를 선택해서 풀면 된다고 생각했고, DFS로 풀기로 했다.

하지만 모두 구현하고 나서 풀리지 않는 문제가 생겼다. 종료 조건에 사용할 depth를 정할 수가 없다는 것이었다.

만약 종료조건이 없거나 널널하다면 DSLR순서로 깊이 우선 탐색을 진행하기 때문에 정답이 LLL일 때 DDDDDDDDDDD..., DDDDDSD..... 와 같이 삥돌아 정답을 향해가게 된다. 

이를 방지하고자 제한 depth를 5정도로 설정한다고 하면, 예를 들어 DDDDDL이 정답인 상황에서는 문제를 해결할 수 없는 것이다.

결론적으로 DFS를 사용하게 되면 딜레마가 발생한다는 것이다.

 

패배를 인정하고 구글링해보았다. 그리고 거의 모든 사람들이 BFS풀었다는 걸 알게 됐다. 

BFS를 사용한 근거로는 DFS와 BFS는 모두 완전탐색이긴 하지만 depth가 끝도 없이 깊어질 우려가 있는 경우에는 너비 우선 탐색만이 문제를 해결할 수 있다는 것이다.

 

그동안 완전탐색해야하는 문제는 DFS나 BFS 둘 중 어느 것을 사용해도 상관없다고 생각해왔다. 하지만 위에서 말한 것 처럼 문제에 따라 적합한 알고리즘이 존재할 수 있다는 걸 알게 됐다. 

 

앞으로는 적용할 수 있는 여러 알고리즘이 떠오른다고 할 때 어떤 게 가장 적합한지 개념에 입각해 생각해보는 것이 필요해보인다.

 

아래는 BFS로 다시 푼 코드이다.

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

class Main {
    static class Register {
        int cnt;
        StringBuilder cmd;
        int current;

        public Register(int cnt, StringBuilder cmd, int current) {
            this.cnt = cnt;
            this.cmd = cmd;
            this.current = current;
        }
    }

    private static int idx = 0;
    private static String[] cmds;
    private static final String[] cmdMapper = {"D", "S", "L", "R"};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        cmds = new String[T];

        for (int i = 0; i < T; i++) {
            String[] input = br.readLine().split(" ");
            int A = Integer.parseInt(input[0]);
            int B = Integer.parseInt(input[1]);

            bfs(A, B);
            idx++;
        }

        Arrays.stream(cmds).forEach(System.out::println);
    }

    private static void bfs(int A, int answer) {
        Queue<Register> q = new LinkedList<>();
        q.offer(new Register(0, new StringBuilder(), A));

        while (!q.isEmpty()) {
            Register polled = q.poll();

            for (int i = 0; i < 4; i++) {
                int calculatedCurrent = calc(polled.current, i);

                //시간 복잡도 개선(q.poll시 검증 -> enqueue전 검증)
                if (calculatedCurrent == answer) {
                    cmds[idx] = polled.cmd.append(cmdMapper[i]).toString();
                    return;
                }

                q.offer(new Register(polled.cnt + 1,
                        new StringBuilder(polled.cmd.toString()).append(cmdMapper[i]),
                        calculatedCurrent));
            }
        }
    }

    private static int calc(int current, int flag) {
        //D
        if (flag == 0) {
            return current * 2 % 10000;
        }
        //S
        if (flag == 1) {
            if (current == 0) {
                return 9999;
            }
            return current - 1;
        }
        //L
        int d1 = current / 1000;
        int d2 = (current-d1*1000) / 100;
        int d3 = (current-d1*1000-d2*100) / 10;
        int d4 = current % 10;
        if (flag == 2) {
            int res = current - d1 * 1000;
            return res * 10 + d1;
        }
        //R
        return d4 * 1000 + d1 * 100 + d2 * 10 + d3;
    }
}

결론부터 말하면 위 코드는 메모리 초과로 오답처리를 받았다.

처음에는 StringBuilder를 너무 많이 사용한 게 원인이라고 생각해서 숫자를 다루도록 위 코드로 변경했지만 똑같이 메모리 초과가 발생했다.

뭐가 문제일까 곰곰히 생각해보고 디버깅 해본 결과, calc메서드를 통해 D,S,L,R 중 하나로 연산한 결과가 중복발생하는 경우가 있었다.

그래서 다음과 같이 고쳤다.  

최종 코드

/*
A와 레지스터에 저장된 값을 누산한다. 이 때 DFS로 풀 경우 결과값 B를 찾기 위해 depth가 무한히 깊어질 수 있으므로 BFS를 이용해 최단거리로 결과값 B를 구한다.
또한 최적화를 위해 visited 배열을 사용하는데 현재 값과 레지스터의 값을 연산한 값이 이미 도출된 적 있는 값이면 continue한다.
*/

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

class Main {
    static class Register {
        int cnt;
        StringBuilder cmd;
        int current;

        public Register(int cnt, StringBuilder cmd, int current) {
            this.cnt = cnt;
            this.cmd = cmd;
            this.current = current;
        }
    }

    private static int idx = 0;
    private static String[] cmds;
    private static final String[] cmdMapper = {"D", "S", "L", "R"};
    private static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        cmds = new String[T];

        for (int i = 0; i < T; i++) {
            String[] input = br.readLine().split(" ");
            int A = Integer.parseInt(input[0]);
            int B = Integer.parseInt(input[1]);
            visited = new boolean[10000];

            bfs(A, B);
            idx++;
        }

        Arrays.stream(cmds).forEach(System.out::println);
    }

    private static void bfs(int A, int answer) {
        Queue<Register> q = new LinkedList<>();
        q.offer(new Register(0, new StringBuilder(), A));

        while (!q.isEmpty()) {
            Register polled = q.poll();

            for (int i = 0; i < 4; i++) {
                int calculatedCurrent = calc(polled.current, i);

                //이미 도출된 결과값이 다시 나오는 경우 여기서 부터 가장 빠르게 B를 계산한다고 해도 그 값이 절대 최단거리일 수 없다.
                // 그전에 나왔던 것에서 가장 빠르게 계산한 결과가 더 최단거리이기 때문이다.
                // 따라서 visited를 이용한 가지치기가 유효하게 된다.
                if (visited[calculatedCurrent]) {
                    continue;
                }
                visited[calculatedCurrent] = true;

                //시간 복잡도 개선(q.poll시 검증 -> enqueue전 검증)
                if (calculatedCurrent == answer) {
                    cmds[idx] = polled.cmd.append(cmdMapper[i]).toString();
                    return;
                }

                q.offer(new Register(polled.cnt + 1,
                        new StringBuilder(polled.cmd.toString()).append(cmdMapper[i]),
                        calculatedCurrent));
            }
        }
    }

    private static int calc(int current, int flag) {
        //D
        if (flag == 0) {
            return current * 2 % 10000;
        }
        //S
        if (flag == 1) {
            if (current == 0) {
                return 9999;
            }
            return current - 1;
        }
        int d1 = current / 1000;
        int d2 = (current - d1 * 1000) / 100;
        int d3 = (current - d1 * 1000 - d2 * 100) / 10;
        int d4 = current % 10;

        //L
        if (flag == 2) {
            int res = current - d1 * 1000;
            return res * 10 + d1;
        }
        //R
        return d4 * 1000 + d1 * 100 + d2 * 10 + d3;
    }
}

visited배열을 생성해 하나의 테스트 케이스에서 이미 연산된 결과가 다시 나올 경우 enqueue하지 않도록 구현했다.

주어지는 숫자는 1~9999이므로 visited배열의 크기를 10000으로 하여 계산된 결과를 인덱스로 사용해 문제를 해결할 수 있었다.