[백준_9019번] DSLR

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

9019번: DSLR

[문제]

 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)

1. D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
2. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
3. L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
4. R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

 

 위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다. 여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.

 

1234 →L 2341 →L 3412
1234 →R 4123 →R 3412

 

 따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다. n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.

 

[입력 조건]

 프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.

 

[코드]

import java.util.*;

class Command {
	int num;
	String result; // num이라는 숫자가 도출되기 까지 수행한 연산
	
	public Command(int num, String result) {
		this.num=num;
		this.result=result;
	}
}
public class BaekJoon_9019 {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int tc=sc.nextInt();
		
		while(tc-->0) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			
			boolean[] visited=new boolean[10000]; // 각 숫자가 만들어졌는지 체크하는 배열
			visited[a]=true; // 시작 숫자인 a는 true 처리
			
			Queue<Command> q=new LinkedList<>();
			q.offer(new Command(a,""));
			
			while(!q.isEmpty()) {
				Command c=q.poll();
				int now=c.num;
				// 각 연산
				int D=(now*2)%10000;
				int S=(now==0)?9999:now-1;
				int L=(now%1000)*10+now/1000;
				int R=(now%10)*1000+now/10;
				
				if(now==b) { // 정답 숫자가 나왔다면 해당 숫자가 도출되기까지 수행한 연산들을 저장한 문자열 출력 후 종료
					System.out.println(c.result);
					break;
				}
				
				/*
				 * 각 연산을 수행한 결과가 한번도 도출된 적 없는 값이라면
				 * 해당 값을 방문처리 해준 후 큐에 값과, 이전 값(now)를 얻고자 수행한 연산들(c.result)에 
				 * 수행한 연산을 더한 값을 삽입한다. 
				 */
				if(!visited[D]) {
					visited[D]=true; 
					q.offer(new Command(D,c.result+"D"));
				}
				
				if(!visited[S]) {
					visited[S]=true;
					q.offer(new Command(S,c.result+"S"));
				}
				
				if(!visited[L]) {
					visited[L]=true;
					q.offer(new Command(L,c.result+"L"));
				}
				
				if(!visited[R]) {
					visited[R]=true;
					q.offer(new Command(R,c.result+"R"));
				}
			}
		}
	}
}

 

[고찰]

 이번 문제는 클래스에 숫자와, 해당 숫자를 도출하기까지 수행한 연산들을 저장한 문자열을 저장하는 것이 핵심이다. 이후에는 B를 만드는 가장 최소한의 연산을 수행해야 하기 때문에 BFS 알고리즘을 사용하면 된다. 큐에서 꺼낸 값(now)에 D,S,L,R을 각각 수행한 값이 이전에 만들어졌는가를 판단하고 만들어지지 않았다면 만들어진 숫자와, now를 만드는데 수행한 연산들의 집합에 새롭게 수행한 연산을 더한 클래스를 큐에 삽입해준다. 이 과정을 진행하다 큐에서 꺼낸 값이 만들고자 하는 B와 같다면 while문을 종료하면 된다.