[BOJ] DSLR

[9019] DSLR

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

• 네 자리 숫자  A와 B가 주어졌을 때
• A -> B로 바꾸는 최소 연산 횟수
• D : N -> 2*N
• S : N -> N-1
• L : 한 자리씩 왼쪽으로
• R : 한 자리씩 오른쪽으로

 

 

Solution

• BFS 풀이방법
• 이 문제는 어떠한 과정을 거쳐야 하는지를 구해야 한다.
• Register 객체를 만들어 연산을 했을 때 어떤 과정을 거쳤는지 저장한다.
• 123에 L 연산을 수행했을 때는 231이 아닌 1230이 계산 결과가 된다.

 

 

소스코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static final int MAX = 10000;
	int a, b;
	Register[] arr;
	boolean c[];

	class Register {
		int num;
		int cnt;
		String op;

		public Register(int num) {
			this.num = num;
			cnt = 0;
			op = "";
		}
	}

	public void go() {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		while (tc-- > 0) {
			a = sc.nextInt();
			b = sc.nextInt();
			arr = new Register[MAX];
			c = new boolean[MAX];
			arr[a] = new Register(a);
			bfs(arr[a]);
			System.out.println(arr[b].op);
		}

	}

	public void bfs(Register n) {
		Queue<Register> q = new LinkedList<>();
		q.offer(n);
		c[n.num] = true;

		while (!q.isEmpty()) {
			Register cur = q.poll();

			int next = (cur.num * 2) % MAX;
			if (!c[next]) {
				arr[next] = new Register(next);
				arr[next].cnt = cur.cnt + 1;
				arr[next].op = cur.op.concat("D");
				q.offer(arr[next]);
				c[next] = true;
			}

			next = cur.num - 1;
			if (next == -1) {
				next = 9999;
			}
			if (!c[next]) {
				arr[next] = new Register(next);
				arr[next].cnt = cur.cnt + 1;
				arr[next].op = cur.op.concat("S");
				q.offer(arr[next]);
				c[next] = true;
			}

			next = (cur.num % 1000) * 10 + (cur.num / 1000);
			if (!c[next]) {
				arr[next] = new Register(next);
				arr[next].cnt = cur.cnt + 1;
				arr[next].op = cur.op.concat("L");
				q.offer(arr[next]);
				c[next] = true;
			}

			next = (cur.num % 10) * 1000 + (cur.num / 10);
			if (!c[next]) {
				arr[next] = new Register(next);
				arr[next].cnt = cur.cnt + 1;
				arr[next].op = cur.op.concat("R");
				q.offer(arr[next]);
				c[next] = true;
			}
		}
	}

	public static void main(String[] args) {
		Main main = new Main();
		main.go();
	}
}