백준 9019 - DSLR

Java

9019 번 - DSLR

문제

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다.

• 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에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.

A 와 B는 모두 0 이상 10,000 미만이다.

접근 방법

중요한건 수의 개수는 10000개 이므로 방문 여부로 체크하여 불필요한 반복을 줄인다.
BFS는 너비 탐색으로, 목표에 도달하는 그 순간이 최소 거리이다.

시작 숫자부터 bfs로 할 수 있는 연산을 체크하여(방문하지 않은) 목표한 수에 도달 할때까지 반복한다.

코드

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

public class Main {
	static int n, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	
    	for(int idx = 0; idx < n; idx++) {
    		stk = new StringTokenizer(br.readLine());
    		
    		boolean[] regi = new boolean[10000];
    		int A = stoi(stk.nextToken());
    		int B = stoi(stk.nextToken());
    		
			// ---------BFS 시작------------
    		Queue<Pair> q = new LinkedList<>();
    		q.add(new Pair(A,""));
    		regi[A] = true;
    		int num, cal;
    		String str;
    		Pair p;
    		while(!q.isEmpty()) {
    			p = q.poll();
    			num = p.num;
    			str = p.str;
    			if(num == B) {
    				System.out.println(str);
    				break;
    			}
    			
    			// D
    			cal = (num * 2) % 10000;
    			if(!regi[cal]) {
    				q.add(new Pair(cal, str + "D"));
    				regi[cal] = true;
    			}
    			
    			// S
    			cal = (num + 9999) % 10000;
    			if(!regi[cal]) {
    				q.add(new Pair(cal, str + "S"));
    				regi[cal] = true;
    			}
    			
    			// L
    			if(num < 999)
    				cal = num * 10;
    			else
    				cal = (num - (num / 1000) * 1000) * 10 + num / 1000;
    				
    			if(!regi[cal]) {
    				q.add(new Pair(cal, str + "L"));
    				regi[cal] = true;
    			}
    			
    			// R
    			if(num % 10 == 0)
    				cal = num / 10;
    			else
    				cal = num / 10 + num % 10 * 1000;
    			
    			if(!regi[cal]) {
    				q.add(new Pair(cal, str + "R"));
    				regi[cal] = true;
    			}
    		}
    	}
    	
    	br.close();
	}

	static class Pair{
		int num;
		String str;
		Pair(int num, String str){
			this.num = num;
			this.str = str;
		}
		
		@Override
		public String toString() {
			StringBuilder builder = new StringBuilder();
			builder.append("[").append(num).append(", ").append(str).append("]");
			return builder.toString();
		}
	}
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

고민했던 이유는, 연산의 종료 조건을 고려하지 못하여 무한대로 반복 되는 것을 막지 못하였다.
수의 범위가 일정하게 주어져 있으므로, 방문 여부를 담은 배열을 통하여 무한 루프를 막는다.

또한 최단 거리, 반복에 관한 것은 bfs를 고려하는 것도 방법이다.

개선할 점

없습니다.