[백준] 9019번. DSLR(JAVA)

문제

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

---

풀이(25분)

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

public class Main {
    static final int MAX = 10000;
    static boolean[] visited;
    static String[] commands;

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

        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int target = Integer.parseInt(st.nextToken());

            System.out.println(processTestCase(start, target));
        }
    }

    static String processTestCase(int start, int target) {
        Queue<Integer> queue = new LinkedList<>();
        visited = new boolean[MAX];
        commands = new String[MAX];
        Arrays.fill(commands, "");

        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int current = queue.poll();

            // 4가지 명령어 시도
            tryCommand(queue, current, (current * 2) % MAX, "D");
            tryCommand(queue, current, current == 0 ? 9999 : current - 1, "S");
            tryCommand(queue, current, (current % 1000) * 10 + current / 1000, "L");
            tryCommand(queue, current, (current % 10) * 1000 + current / 10, "R");

            if (visited[target]) break;
        }

        return commands[target];
    }

    /**
     * 명령어를 적용한 결과 숫자가 아직 방문되지 않았을 경우,
     * 큐에 추가하고, 명령어 누적 결과도 저장한다.
     */
    static void tryCommand(Queue<Integer> queue, int from, int to, String cmd) {
        if (!visited[to]) {
            visited[to] = true;
            queue.add(to);
            commands[to] = commands[from] + cmd;
        }
    }
}

---

문제 풀이 전략

 

BFS를 통해 매번 4개의 명령어를 전부 실행한다. 

이 과정에서 visited인 방문 배열을 통해 이미 체크했던 숫자에 대해서는 더 이상 체크하지 않도록 한다.

 

bfs와 방문배열에 대한 개념을 확장하는 것이 중요하다고 느껴진 문제이다.

익숙한 개념일 수록 다양하게 접근하고 확장하자!