[Baekjoon] DSLR - Java

문제

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

 

풀이

네자릿수를 저장하는 레지스터에서 D, S, L, R의 네가지 명령어를 수행하는데 주어진 숫자를 만들기 위한 최소한의 명령어를 구하는 문제이다.

 

이 문제를 명령을 수행해서 갈 수 있는 최소의 거리를 구하면 된다고 생각했고, 최소 거리를 구하면서 명령어도 같이 저장하면 될 것이라고 생각해 bfs를 사용해서 구현하면 된다고 생각했다.

 

1. 변환 전, 후 숫자를 입력받는다.

 

2. bfs를 사용해서 D, S, L, R과 같은 명령어를 수행했을 때, 방문 처리가 되지 않았으면 명령어를 같이 저장하면서 bfs를 수행한다.

 

3. 변환 후 숫자에 도달 했을 경우, 그에 대한 명령어를 출력한다.

 

소스코드

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

public class Main {
    static class Info {
        int num;
        String comm;

        Info(int num, String comm) {
            this.num = num;
            this.comm = comm;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = null;

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

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            sb.append(bfs(a, b)).append("\n");
        }

        System.out.print(sb);

        br.close();
    }

    static String bfs(int a, int b) {
        ArrayDeque<Info> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[10001];

        queue.addLast(new Info(a, ""));
        visited[a] = true;

        while (!queue.isEmpty()) {
            Info info = queue.removeFirst();

            int num = info.num;
            String comm = info.comm;

            if (num == b) {
                return comm;
            }

            int d = (2 * num) % 10000;
            int s = num - 1;
            int l = (num / 1000) + ((num % 1000) * 10);
            int r = ((num % 10) * 1000) + (num / 10);

            if (s < 0) s = 9999;

            if (!visited[d]) {
                queue.addLast(new Info(d, comm + "D"));
                visited[d] = true;
            }

            if (!visited[s]) {
                queue.addLast(new Info(s, comm + "S"));
                visited[s] = true;
            }

            if (!visited[l]) {
                queue.addLast(new Info(l, comm + "L"));
                visited[l] = true;
            }

            if (!visited[r]) {
                queue.addLast(new Info(r, comm + "R"));
                visited[r] = true;
            }
        }

        return "";
    }
}

 

실행결과