[JAVA] 백준 - 9019 DSLR

Solved.ac class 에서 풀어볼만한 문제들이 많아서 풀고있다.

백준 online judge 에서 어떤 문제를 풀어야할지 모르겠다면 class문제들을 풀어보는 것을 추천한다.

 

DSLR 문제는 class 3++ 문제 중 정답률도 낮고 상당히 난이도 있는 문제였다.

 

🤔 초기 문제 접근

Original 숫자가 Target 숫자가 되기 위해서 DSLR 명령어를 사용해 가능한 모든 경우의 수 중

제일 짧은 명령어를 찾는 문제이기 때문에 완전 탐색 문제라고 생각했다.

초기 코드의 흐름은 재귀적인 방법으로, DSLR 명령어를 수행한 값을 다시 parameter로 넣어주며

StringBuilder 에 명령어를 append 해주는 방식이었다.

이때 num(parameter) == target이면 result 문자열과 현재 StringBuilder 중 더 짧은 쪽은 result로

갱신해주는 것으로 생각했다.

 

하지만 이는 잘못된 접근이었다. 언제 어떤 명령어를 써야할지 몰랐기 때문, 결과적으로

D연산자만 계속 수행되고.. Stack Overflow가 났다..

 

✅ 핵심 풀이

Original == A, Target == B

문제 조건으로 Original과 Target 모두 최소 0, 최대 9999 내에서 주어진다고 되어 있기 때문에

visited, operation 배열의 최대 크기는 10000 이다.

어떤 수 num 이 있을 때, 해당 수에 DSLR연산을 수행한 것이 index가 되어

visited[index]가 아직 방문하지 않았다면 방문처리하고 operation[index] 역시 방문처리를 해준다.

Original 에서 어떤 수 num이 되기 위해서 수행했던 연산자가 stack형식으로 쌓인다고 생각하면 된다.

최종적으로 visited[target] = true를 만족하면 while loop 가 끝나고 

operation[target]에 현재까지 저장된 연산자 String을 출력하게 된다.

그림으로 대충 표현하자면 위와 같다고 할 수 있다.

 

 

🚨Code

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i = 0; i<T; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int original = Integer.parseInt(st.nextToken());
			int target = Integer.parseInt(st.nextToken());
			
			Queue<Integer> q = new LinkedList<>();
			boolean[] visited = new boolean[10000];
			String[] operation = new String[10000];
			
			q.add(original);
			visited[original] = true;
			Arrays.fill(operation, "");
			
			while(!q.isEmpty() && !visited[target]) {
				int num = q.poll();
				
				int d = (num * 2) % 10000;
				int s = num == 0 ? 9999 : num -1;
				// num % 1000 -> d2d3d4, num / 1000 -> d1
				int l = (num % 1000) * 10 + num / 1000; 
				// num % 10 -> d4, num / 10 -> d2d3d4
				int r = (num % 10) * 1000 + num / 10;
				
				if(!visited[d]) {
					q.add(d);
					visited[d] = true;
					operation[d] = operation[num] + "D";
				}
				if(!visited[s]) {
					q.add(s);
					visited[s] = true;
					operation[s] = operation[num] + "S";
				}
				if(!visited[l]) {
					q.add(l);
					visited[l] = true;
					operation[l] = operation[num] + "L";
				}
				if(!visited[r]) {
					q.add(r);
					visited[r] = true;
					operation[r] = operation[num] + "R";
				}
			}
				
			System.out.println(operation[target]);	
		}
	}
}