BOJ_G4_9019

📁 [G4_9019] DSLR

• 시간초과..

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 {

	// 숫자, 함수이름(D,S,L,R)
	static class ch {
		int num;
		String ch;

		public ch(int num, String ch) {
			this.num = num;
			this.ch = ch;
		}

	}

	static int A, B;
	static Queue<ch> queue;
	static String res;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		// **** input start ****
		int T = Integer.parseInt(br.readLine());

		for (int tc = 0; tc < T; tc++) {
			st = new StringTokenizer(br.readLine(), " ");
			A = Integer.parseInt(st.nextToken());
			B = Integer.parseInt(st.nextToken());

		// **** input end ****

		String[] DSLR = { "D", "S", "L", "R" };
		int min = Integer.MAX_VALUE;
		String output = "";
		// 4 순서대로 넣어보기
		for (int i = 0; i < 4; i++) {
			res = "";
			queue = new LinkedList<ch>();
			queue.add(new ch(A, DSLR[i]));
			BFS();

			min = Math.min(min, res.length());
			if(min == res.length()) {
				output = res;
			}
		}
		sb.append(output).append("\n");
		}
		System.out.println(sb);
	} // main end

	// BFS
	static void BFS() {
		while (!queue.isEmpty()) {
			ch c = queue.poll();
			int temp = c.num;
			String str = c.ch;

			// B로 되면
			if (temp == B) {
				str = str.substring(1, str.length());
				res += str;
				break;
			}

			// DSLR 순서대로

			// D
			queue.add(new ch(D(temp), str + "D"));

			// S
			queue.add(new ch(S(temp), str + "S"));

			// L
			queue.add(new ch(L(temp), str + "L"));

			// R
			queue.add(new ch(R(temp), str + "R"));

		}

	}

	// D = 2*N
	static int D(int num) {
		num *= 2;

		// 만약 곱하기 2한 값이 9999보다 클경우 mod 10000 해주기
		if (num > 9999)
			num %= 10000;
		return num;
	}

	// S = N-1
	static int S(int num) {
		num -= 1;

		// 1 뺀 값이 0일 경우 9999 저장
		if (num == 0)
			num = 9999;
		return num;
	}

	// L = left
	static int L(int num) {
		int temp = num;

		int thousand = (temp / 1000);
		temp %= 1000;
		int hundred = (temp / 100);
		temp %= 100;
		int ten = (temp / 10);
		temp %= 10;
		int one = temp;

		num = hundred * 1000 + ten * 100 + one * 10 + thousand;
		return num;
	}

	// R = right
	static int R(int num) {
		int temp = num;

		int thousand = (temp / 1000);
		temp %= 1000;
		int hundred = (temp / 100);
		temp %= 100;
		int ten = (temp / 10);
		temp %= 10;
		int one = temp;

		num = one * 1000 + thousand * 100 + hundred * 10 + ten;
		return num;
	}
} // class end

• 찾은 방법..

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

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;

		// **** input start ****
		int T = Integer.parseInt(br.readLine());

		for (int tc = 0; tc < T; tc++) {
			st = new StringTokenizer(br.readLine(), " ");
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			// **** input end ****

			boolean[] v = new boolean[10000];
			String[] command = new String[10000];
			Queue<Integer> queue = new LinkedList<Integer>();

			queue.add(A);
			// 방문처리
			v[A] = true;
			Arrays.fill(command, "");

			while (!queue.isEmpty() && !v[B]) {
				int temp = queue.poll();

				// DSLR
				int D = (temp * 2) % 10000;
				int S = temp == 0 ? 9999 : temp - 1;
				int L = (temp % 1000) * 10 + (temp / 1000);
				int R = (temp % 10) * 1000 + (temp / 10);

				if (!v[D]) {
					// 방문처리
					v[D] = true;
					// 문자 추가
					command[D] = command[temp] + "D";
					// queue 더하기
					queue.add(D);
				}
				if (!v[S]) {
					// 방문처리
					v[S] = true;
					// 문자 추가
					command[S] = command[temp] + "S";
					// queue 더하기
					queue.add(S);
				}
				if (!v[L]) {
					// 방문처리
					v[L] = true;
					// 문자 추가
					command[L] = command[temp] + "L";
					// queue 더하기
					queue.add(L);
				}
				if (!v[R]) {
					// 방문처리
					v[R] = true;
					// 문자 추가
					command[R] = command[temp] + "R";
					// queue 더하기
					queue.add(R);
				}
			}
			sb.append(command[B]).append("\n");
		}
		System.out.println(sb);
	} // main end
} // class end

🤔 나의 생각

처음에 BFS () + DSLR 을 이용해서 풀었다.
그러나 .. 시간초과..
그래서 찾아보니 방문처리가 시간초과의 원인이였다.
그리고 나는 수와 문자를 class로 따로 둬서 둘 다 고려해줬는데 그럴 필요 없이 수로만 체크하고 문자는 배열을 이용해 최대 10000이니 10000개를 가진 배열에서 문자를 저장해주면 되는 것이였다.
이건 생각지도 못한..
그리고 방문처리를 통해 확인.
또한 ‘L’,’R’을 구할때 어차피 규칙적으로 이동하니 곱하고 나누기만 해주면 더 간단했다.
그래도 BFS로 접근한 것이 아주 만족스.. 왜 방문처리를 까먹었을까..
아숩다..