[문제 풀이] 백준 9019번 DSLR JAVA

문제

  문제접근 방법   

해당 문제는 정수 A를 네 가지 연산 D, S, L, R을 이용해 정수 B로 바꾸는 최단 연산 시퀀스를 구하는 과제이다. 입력은 테스트 케이스 수 T와 각 케이스의 두 정수 A, B(0~9999)이다. 출력은 A에서 B로 도달하는 최소 연산들의 문자열이다. 상태 공간은 0000부터 9999까지 10,000개 정수로 한정되며, 각 연산의 비용이 동일하므로 한 케이스당 최대 10,000개 상태와 각 상태당 4개의 전이를 고려하면 충분하다. 결국 핵심은 최단 경로를 보장하는 탐색을 수행하고, 그 결과를 연산 문자열로 복원하는 일이다.

접근 방식은 BFS로 상태를 확장하며 목표를 만나면 즉시 중단하고, 탐색 중 기록한 이전 상태와 사용 연산을 이용해 역추적으로 연산 문자열을 복원하는 식으로 코드를 구현해보고자 한다

< 최종 코드 >

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

public class Main {
    static String bfs(int start, int target) {
        boolean[] visited = new boolean[10000];
        int[] from = new int[10000];
        char[] how = new char[10000];
        ArrayDeque<Integer> q = new ArrayDeque<>();
        q.add(start);
        visited[start] = true;
        while (!q.isEmpty()) {
            int x = q.poll();
            if (x == target) break;

            int d = (x * 2) % 10000;
            if (!visited[d]) { visited[d] = true; from[d] = x; how[d] = 'D'; q.add(d); }

            int s = (x == 0) ? 9999 : x - 1;
            if (!visited[s]) { visited[s] = true; from[s] = x; how[s] = 'S'; q.add(s); }

            int l = (x % 1000) * 10 + x / 1000;
            if (!visited[l]) { visited[l] = true; from[l] = x; how[l] = 'L'; q.add(l); }

            int r = (x % 10) * 1000 + x / 10;
            if (!visited[r]) { visited[r] = true; from[r] = x; how[r] = 'R'; q.add(r); }
        }
        StringBuilder sb = new StringBuilder();
        int cur = target;
        while (cur != start) {
            sb.append(how[cur]);
            cur = from[cur];
        }
        return sb.reverse().toString();
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            out.append(bfs(A, B)).append('\n');
        }
        System.out.print(out.toString());
    }
}

최종 코드의 흐름은 다음과 같다. 입력을 받아 테스트 케이스마다 A와 B를 읽고, 각 케이스별로 BFS를 초기화하고 시작 상태 A를 큐에 넣고 방문 처리하며, 이전 상태(from)와 사용 연산(how)을 기록할 준비를 한다. 큐에서 상태 x를 꺼낼 때마다 D, S, L, R 연산으로 다음 상태를 계산하고, 미방문이면 방문 처리 후 from/how를 기록하고 큐에 넣는다. 탐색 중 목표 상태 B를 만나면 더 이상 확장하지 않고 탐색을 중단한다. from/how 배열을 이용해 B에서 A까지 거슬러 올라가며 연산 문자를 수집한 뒤, 이를 뒤집어 최종 답 문자열로 만들고 각 케이스의 답을 출력 버퍼에 누적하고, 모든 케이스 처리가 끝나면 한꺼번에 출력하는 식으로 동작한다.

 

  마무리  

dfs를 활용해 접근해야겠다는 생각은 했지만 다른 아이디어를 떠올리는데 어려움이 있던 문제로 꼭 한 번 풀어보는 것을 추천한다.