[백준/BOJ] 9019 - DSLR (G4/Java)

문제 링크

9019번: DSLR

🏷️ 카테고리

`#그래프 이론` `#그래프 탐색` `#너비 우선 탐색`

⏳ 시간복잡도

각 테스트 케이스 당 최대 1만회

 

📒 해설

개인적으로 여러번 틀린 방향으로 접근을 해서, 굉장히 많이 틀렸던 문제입니다. 문제 내용을 정확하게 숙지하고 풀면 저와 같은 일은 일어나지 않을 것입니다. 해당 문제에서 신경써야 할 부분으로는 '명령어 수행 코드 작성', '레지스터 표현 자료구조 생각하기', '어떤 명령어를 선택할지' ,'지금까지 수행한 명령을 어떻게 기록할지'로 4가지 정도 될 것 같습니다. 그럼 이 4가지를 신경쓰면서 문제를 접근하겠습니다.

 

📜 문제 조건

 

문제의 조건은 다음과 같습니다.

• T개의 테스트 케이스가 주어진다
• 각 테스크 케이스에서는 0이상 10000이하의 정수 A와 B가 주어진다
• A가 DSLR 연산을 거쳐서 B가 될 수 있는 최소한의 명령어를 한 줄씩 출력을 한다.

 

🔍 문제 접근

위에서 작성한 4가지 신경써야 할 포인트들을 고려하며 풀이 방법을 찾아야 합니다.

 

가장 먼저 신경써야 할 부분은 레지스터 표현 자료구조 생각하기입니다.

문제에서 설명했듯이 레지스터는 d1, d2, d3, d4 4가지 숫자로 이루어져 있고, 앞자리가 0이 된다면, 실제 수는 0을 제외하고 표현을 해줘야 했습니다. 

처음엔 위의 조건을 크게 신경쓰지 않고 하나의 int로 구성을 했었는데, 그렇게 할 경우 풀 수 없는 케이스들이 존재했습니다.

 

고려한 구조는 아래와 같습니다. 바로 d1, d2, d3, d4를 모두 포함하고 있으며, 실제 표현될 수 역시 가지고 있는 구조를 생각했습니다.

 

static class Register {
    int d1;
    int d2;
    int d3;
    int d4;
    int value;
    public Register(int value, Record record) {
        this.d1 = value/1000;
        this.d2 = value/100 % 10;
        this.d3 = value/10 % 10;
        this.d4 = value % 10;
        this.value = value;
    }
}

 

레지스터의 구조를 설계를 했기 때문에, '명령어 수행 코드 작성'은 큰 문제가 없습니다. Register의 변수를 조작하면 큰 어려움이 없기 때문입니다.

 

'어떤 명령어를 선택할지'는 이 문제가 최소 명령 수행 횟수를 원하기 때문에, BFS의 형태로 진행하려고 했습니다. 이전에 깊게 생각하지 않고, DFS로 진행한 결과 'D' 명령어에 의해서 무한루프를 도는 경우가 발생습니다. 최소 명령 수행 횟수가 문제에서 주어졌으면, 반드시 BFS를 우선적으로 고려해야합니다.

 

마지막 고려사항은 ' 지금까지 수행한 명령을 어떻게 기록할지' 입니다. BFS를 진행하면, Queue에서 dequeue된 값이 어떤 과정을 거쳐서 나왔는지에 대해서 알 수 없기 때문에, 그 과정을 기록할 자료구조를 만들고, 이를 Register에 넣어주는 식으로 접근했습니다.

 

🔑 문제 풀이

 

사용 변수

static char[] commands = {'D', 'S', 'L', 'R'}; // 주어진 명령
static boolean[] visited; // BFS를 돌면서 특정 숫자에 위치했는지 체크
static class Register {
    int d1;
    int d2;
    int d3;
    int d4;
    int value;
    Record record;

    public Register(int value, Record record) {
        this.d1 = value/1000;
        this.d2 = value/100 % 10;
        this.d3 = value/10 % 10;
        this.d4 = value % 10;
        this.value = value;
        this.record = record;
    }
    
}
static class Record { // Register가 어떤 연산을 거쳤는지 기록, 연결 리스트로 구현

    char command;
    Record next;

    public Record(char command, Record next) {
        this.command = command;
        this.next = next;
    }
}

위에 코드에서 추가로 설명이 필요한 것은 '지금까지 수행한 명령을 어떻게 기록할지'  를 고려했던 Record 클래스입니다. Record 클래스는 Register가 거쳐온 명령을 연결 리스트 형태로 가지고 있도록 했습니다.

 

명령어 수행

static int action(char command, int d1, int d2, int d3, int d4, int value) {

    switch (command) {
        case 'D':
            value = (value * 2 ) % 10000;
            break;
        case 'S':
            if(value == 0)
                value = 9999;
            else value--;
            break;
        case 'L':
            value = d2*1000 + d3 * 100 + d4 * 10 + d1;
            break;
        case 'R':
            // 마지막을 앞으로 보내기
            value = d4*1000 + d1 * 100 + d2 * 10 + d3;
            break;
    }
    return value;
}

위는 명령어 수행 코드입니다. 각 명령어에 대해서 다시 리마인드하면 아래와 같습니다.

• D : 수를 2배로 만들고, 9999를 넘으면 10000으로 나눈 나머지를 레지스터에 저장한다.
• S : 수에서 1뺀 값을 레지스터에 저장한다. 이때 수가 0이라면 9999를 저장한다.
• L : 각 자리수를 왼쪽으로 이동시킨다. d1d2d3d4의 형태라면 d2d3d4d1의 형태로 변경한다.
• R : 각 자리수를 오른쪽으로 이동시킨다. d1d2d3d4의 형태라면 d4d1d2d3의 형태로 변경한다.

앞서서 Register의 자료구조를 각 자리수와 수로 표현했을 때를 변수로 갖고있기 때문에, 연산에 큰 어려움은 없었습니다.

 

BFS

static Register bfs(int from, int to){
    Queue<Register> q = new ArrayDeque<>();
    Register start = new Register(from,null);

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

        for (char command : commands) {
            int action = action(command, poll.d1, poll.d2, poll.d3, poll.d4, poll.value);
            if (!visited[action]) {
                visited[action] = true;
                Register register = new Register(action, new Record(command, poll.record));
                if (action == to) {
                    return register;
                }
                q.add(register);
            }
        }
    }
    return null;
}

BFS를 통해 각 명령어를 수행했습니다. 명령어를 수행하는 과정에서 특정 수의 형태를 띈 적이 있다면, visited로 체크해주어 그 수에서 다시 연산을 하지 않도록 처리해주었습니다.

연산을 수행하는 과정에서 목표(to)와 동일하게 된다면, 탐색을 종료했습니다.

 

기록 출력

Record record = (bfs(from, to)).record;
StringBuilder temp = new StringBuilder();
while (record != null) {
    temp.append(record.command);
    record = record.next;
}
sb.append(temp.reverse()).append("\n");

Register가 어떤 명령을 수행했는지 기록하는 Record 클래스는 연결 리스트 형태지만, Stack의 형태를 띄고 있습니다. 그래서 각 명령을 다른 StringBuilder에 담아주고, 그 값의 역순을 정답을 출력할 StringBuilder에 담아주었습니다. 

 

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;



public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static char[] commands = {'D', 'S', 'L', 'R'};
    static boolean[] visited;

    public static void main(String[] args) throws Exception {


        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            visited = new boolean[10001];
            Record record = (bfs(from, to)).record;
            StringBuilder temp = new StringBuilder();
            while (record != null) {
                temp.append(record.command);
                record = record.next;
            }
            sb.append(temp.reverse()).append("\n");
        }
        System.out.print(sb);
    }

    static Register bfs(int from, int to){
        Queue<Register> q = new ArrayDeque<>();
        Register start = new Register(from,null);

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

            for (char command : commands) {
                int action = action(command, poll.d1, poll.d2, poll.d3, poll.d4, poll.value);
                if (!visited[action]) {
                    visited[action] = true;
                    Register register = new Register(action, new Record(command, poll.record));
                    if (action == to) {
                        return register;
                    }
                    q.add(register);
                }
            }
        }
        return null;
    }


    static int action(char command, int d1, int d2, int d3, int d4, int value) {

        switch (command) {
            case 'D':
                value = (value * 2 ) % 10000;
                break;
            case 'S':
                if(value == 0)
                    value = 9999;
                else value--;
                break;
            case 'L':
                value = d2*1000 + d3 * 100 + d4 * 10 + d1;
                break;
            case 'R':
                // 마지막을 앞으로 보내기
                value = d4*1000 + d1 * 100 + d2 * 10 + d3;
                break;
        }
        return value;
    }

    static class Register {
        int d1;
        int d2;
        int d3;
        int d4;
        int value;
        Record record;

        public Register(int value, Record record) {
            this.d1 = value/1000;
            this.d2 = value/100 % 10;
            this.d3 = value/10 % 10;
            this.d4 = value % 10;
            this.value = value;
            this.record = record;
        }

    }
    static class Record {

        char command;
        Record next;

        public Record(char command, Record next) {
            this.command = command;
            this.next = next;
        }
    }



}

결과

레지스터를 표현한 자료구조를 너무 늦게 생각해서 굉장히 많이 틀렸던 문제였다.