9019

DSRL

 

 

 

 

기존작성 코드:

숏코드와 비교했을 때, 개선할 점.

 

1. Op class 대신 ans 배열 사용

2. L,R 연산의 간소화 Register 배열 사용 없이 정수 연산으로만 가능.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static boolean DBG = false;
	static boolean[] visitied;
	static int[] d = { 1000, 100, 10, 1 };

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());

		for (int t = 0; t < N; ++t) {
			st = new StringTokenizer(br.readLine());
			int in = Integer.parseInt(st.nextToken());
			int out = Integer.parseInt(st.nextToken());
			System.out.println(bfs(in, out));
		}

	}

	private static String bfs(int in, int out) {
		visitied = new boolean[10000];
		Queue<Op> Q = new LinkedList<>();
		Q.offer(new Op(in, ""));

		while (!Q.isEmpty()) {
			int size = Q.size();

			for (int i = 0; i < size; ++i) {
				Op op = Q.poll();
				if (op.value == out) {
					return op.history;
				}
				
				if( op.value <  0 || visitied[op.value] ) continue;
				
				visitied[op.value]=true;
				Q.offer(new Op(D(op.value), op.history + "D"));
				Q.offer(new Op(S(op.value), op.history + "S"));
				Q.offer(new Op(L(op.value), op.history + "L"));
				Q.offer(new Op(R(op.value), op.history + "R"));

			}

		}

		return "";
	}

	static int D(int value) {
		return value * 2 % 10000;
	}

	static int S(int value) {
		return (value == 0) ? 9999 : value - 1;
	}

	static int L(int value) {

		int[] register = new int[4];

		for (int i = 0; i < 4; i++) {
			register[i] = value / d[i];
			value %= d[i];
		}

		int tmp = register[0];
		for (int i = 1; i < 4; i++) {
			register[i - 1] = register[i];
		}
		register[3] = tmp;

		int newNumber = 0;
		for (int i = 0; i < 4; i++) {
			newNumber += register[i] * d[i];
		}
		return newNumber;
	}

	static int R(int value) {

		int[] register = new int[4];

		for (int i = 0; i < 4; i++) {
			register[i] = value / d[i];
			value %= d[i];
		}

		int tmp = register[3];
		for (int i = 2; i >= 0; i--) {
			register[i + 1] = register[i];
		}
		register[0] = tmp;

		int newNumber = 0;
		for (int i = 0; i < 4; i++) {
			newNumber += register[i] * d[i];
		}
		return newNumber;
	}
}

class Op {
	int value;
	String history;

	Op(int value, String history) {
		this.value = value;
		this.history = history;
	}

}

 

 

 

참조한 숏코드 : https://www.acmicpc.net/source/14994855

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static boolean DBG = false;
	static boolean[] visitied;
	static String[] ans;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());

		for (int t = 0; t < N; ++t) {
			st = new StringTokenizer(br.readLine());
			int in = Integer.parseInt(st.nextToken());
			int out = Integer.parseInt(st.nextToken());
			// test

			/*
			 * System.out.println("D : "+ D(in)); System.out.println("S : "+ S(0));
			 * System.out.println("L : "+ L(in)); System.out.println("R : "+ R(in));
			 */
			;
			
			System.out.println(bfs(in, out));
		}

	}

	private static String bfs(int in, int out) {
		visitied = new boolean[10000];
		ans = new String[10000];
		Queue<Integer> Q = new LinkedList<>();
		Q.offer(in);
		visitied[in] = true;
		ans[in] = "";

		while (!Q.isEmpty()) {
			int size = Q.size();

			for (int i = 0; i < size; ++i) {
				int now = Q.poll();
				
				if (now == out) {
					return ans[now];
				}

				visitied[now] = true;
				int next = D(now);

				if (!visitied[next]) {
					ans[next] = ans[now] + "D";
					visitied[next] = true;
					Q.offer(next);
				}

				next = S(now);
				if (!visitied[next]) {
					ans[next] = ans[now] + "S";
					visitied[next] = true;
					Q.offer(next);
				}

				next = L(now);
				if (!visitied[next]) {
					ans[next] = ans[now] + "L";
					visitied[next] = true;
					Q.offer(next);
				}
				next = R(now);
				if (!visitied[next]) {
					ans[next] = ans[now] + "R";
					visitied[next] = true;
					Q.offer(next);
				}
			}

		}
		return "";
	}

	static int D(int value) {
		return value * 2 % 10000;
	}

	static int S(int value) {
		return (value == 0) ? 9999 : value - 1;
	}

	static int L(int value) {
		return (value % 1000) * 10 + value / 1000;
	}

	static int R(int value) {
		return (value % 10) * 1000 + value / 10;
	}
}