[백준 9019] DSLR 자바(BFS + 경로 추적)

최근 풀었던 문제 중에 가장 재밌었던 것 같아서 오랜만에 백준 포스팅 😊

 

9019번: DSLR (acmicpc.net)

9019번: DSLR

문제를 간단하게 요약하자면

 

초기값 A

목표값 B  가 주어지면

 

아래 4가지 연산을 통해서 B로 도달할 수 있는 경로를 출력하는 것이다.

 

D 연산: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.

S 연산:  S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.

L 연산: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.

R 연산: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

 

예를 들어,

 

A: 1234 이고 B: 3412 이면

LL 혹은 RR 을 통해서 목표값으로 도달할 수 있고, 정답은 LL 또는 RR 이다. 이는 어떤 연산을 먼저 수행(탐색)해볼 것이냐에 따라서 달라지며, 나올 수 있는 정답의 경우의 수는 여러 개가 될 수 있다. (모두 정답임)

 

어떻게 풀 수 있을까?

 

지난 주, 운영하고 있는 알고리즘 스터디에서 선정했던 문제인

 

숨바꼭질 4 를 풀었다면, 풀이 방향은 쉽게 유추할 수 있을 것이다.

 

초기값 A 노드에서

 

D, S, L, R 에 따른 4 개의 자식 노드가 생기고

 

또 그 자식노드에서도 4 개의 자식노드가 생기고 ...

 

이러한 분기(Branch)를 수행하며 B 값에 도달했는지 확인한다.

 

B 값에 도달했다면,더 이상의 분기를 하지 않고 지금까지 내려온 경로를 출력하면 된다.

 

자, 그래프 탐색 문제로 치환되었다.

 

이제 고민할 것은 DFS / BFS  중 어느 것이 더 효율적인지를 따져보아야 한다.

 

DFS 로 탐색하는 경우에는 효율적이지 않을 것임을 직관적으로 알 수 있을 것이다.

 

깊게 끝까지 (언제 끝날지도 모를) 파고들기 보다는 넓게 넓게 탐색하면서 목표 상태로 도달하는 지 판단하는 것이 좋다.

 

왜냐면?

 

우리는 최단 경로를 출력해야 하기 때문이다.

 

BFS 는 넓게 넓게 탐색하므로, 최초로 목표 상태에 도달했다면 그 떄가 바로 최단 경로인 것이다.

 

DFS 에서는 이를 별도로 관리해주어야 하므로 굉장히 비효율적일 것임을 알 수 있다.

 

자, 그럼 BFS 로 풀이하면 된다.

 

이제 또 고민이다.

 

초기 상태(A) 에 대하여

 

D,S,L,R 연산을 수행한 자식 노드를 탐색하면서 목표 상태(B) 로 도달하는 탐색은 쉽게 구현할 수 있을 것 같은데,

 

초기 상태(A) -> 목표 상태(B) 까지의 경로는 어떻게 저장/출력할 수 있을까?

 

바로 노드에 지금까지 거쳐온 명령어들을 기록하는 것이다.

 

즉,

 

초기 상태의 노드는 (A, "") 이라면

 

D 를 수행한 자식 노드는 (doD(A), "D")

S 를 수행한 자식 노드는 (doS(A), "S")

L 를 수행한 자식 노드는 (doL(A), "L")

R 를 수행한 자식 노드는 (doR(A), "R")

 

이런식으로 노드에 거쳐온 명령어를 기록하자.

 

이를 위해서 Node 클래스에 String 필드를 만들어주고, 큐에 Insert 할 때마다 append 연산을 수행하면 될 것이다.

 

 

 

자바를 사용한다면,

String 에 계속해서 append 연산을 한다는 것은 가령 아래와 같이

str + "R" 이런 식으로 할 텐데

String 은 불변 객체이므로, 내부 구조에 따르면 새로운 String 객체를 만들고 복사하고 append 하는 과정을 거친다.

즉, String 을 이용하는 것은 다소 비효율적인 측면이 존재하며

StringBuilder 을 사용하는 것이 조금 더 최적화할 수 있는 방법일 것이다.

하지만 이 문제는 String 을 사용해도 시간 초과에 걸리지는 않는다. 👍

 만약 시간초과가 발생한다면, String 에 대한 update 를 StringBuilder 으로 바꿔 보는 것이 좋을 것 같다.

그럼에도 불구하고 여전히 시간 초과가 발생한다면 아래의 체크리스트를 확인해보자.

 

1. 갈 필요 없는 노드를 또 방문하려고 하지는 않은지? (사이클 발생 주의) ✔️

2. D,  S, L, R 연산을 비효율적으로 구현한 것은 아닌지? D,S,L,R 연산은 모두 한 줄로 구현 가능하다. L,R 에서 for 문을 사용한다던가 하면 시간 초과가 발생할 수도 있겠다. ✔️

3. 입출력을 BufferedReader, BufferedWriter 을 사용했는지? (Scanner 는 많이 느리다.) ✔️

 

 

아래는 구현 코드이다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        ///System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        int tc = Integer.parseInt(br.readLine());

        while (tc-- > 0) {
            stk = new StringTokenizer(br.readLine());
            boolean[] visited = new boolean[20000];

            int A = Integer.parseInt(stk.nextToken()); // 레지스터의 초깃값
            int B = Integer.parseInt(stk.nextToken()); // 레지스터의 최종값

            Queue<Node> q = new LinkedList<>();
            q.add(new Node(A, ""));
            boolean flag = false;
            while (!q.isEmpty()) {
                if (flag) break;
                Node now = q.poll();
                int t = now.num;
                String str = now.instruction;
                for (Node nn : new Node[]{new Node(doD(t), str + "D"), new Node(doS(t), str + "S"),
                        new Node(doL(t), str + "L"), new Node(doR(t), str + "R")}) {
                    if (visited[nn.num]) continue;
                    if (nn.num == B) {
                        bw.write(nn.instruction + "\n");
                        flag = true;
                        break;
                    }
                    q.add(nn);
                    visited[nn.num] = true;
                }
            }
        }

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

    public static class Node {
        int num;
        String instruction;

        public Node(int num, String instruction) {
            this.num = num;
            this.instruction = instruction;
        }
    }

    public static int doD(int n) {
        return (2 * n) % 10000;
    }

    public static int doS(int n) {
        return n == 0 ? 9999 : n - 1;
    }

    public static int doL(int n) { // 1234 -> 2341
        return (n % 1000) * 10 + (n / 1000);
    }

    public static int doR(int n) { // 1234 -> 4123
        return n / 10 + (n % 10) * 1000;
    }
}

2023. 06. 03.