백준 9019번 : DSLR

BFS 알고리즘을 이용해서 D, S, L, R연산을 반복하며 a가 b가될 때 까지 최소 경로를 찾으면 될 것같다.

 

평소에 풀던 BFS알고리즘 문제와 두 가지 다른 점이 있어서 고민을 했다.

1. visited 처리를 어떻게 해아하는가
2. 평소에는 연산 횟수를 출력하면 됐지만, 이 문제는 어떤 연산을 했는지 연산 순서를 출력해야함

 

먼저 1번 이슈는 vistied 배열을 사용했다.

0~9999까지 숫자가 결과로 나오므로, 연산 결과가 b가 아닌 0~9999사이 숫자는 다시 연산할 필요가 없다
즉 visited[9999] 배열을 선언하여, 해당 숫자를 방문처리하면 된다.

 

2번 이슈는 Queue에 삽입하는 값을 단순 Integer가 아닌, 사용자 정의 클래스를 만들어서 해결했다.

아래 두 정보를 저장하는 사용자 정의 클래스이다.

• 계산 결과인 value
• 연산 종류인 operations

연산 종류 문자열을 계속 이어붙여서 마지막에 출력하면 정답이 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int T = Integer.parseInt(br.readLine());

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

			String result = bfs(A, B);
			bw.write(result + "\n");
		}

		bw.flush();
		bw.close();
		br.close();
	}

	// D 명령어: n을 두 배로 바꿔 10000으로 나눈 나머지를 취함
	public static int D(int n) {
		return (2 * n) % 10000;
	}

	// S 명령어: n에서 1을 뺀 결과를 반환 (n이 0이면 9999 반환)
	public static int S(int n) {
		return (n == 0) ? 9999 : n - 1;
	}

	// L 명령어: n의 자릿수를 왼쪽으로 회전시킴
	public static int L(int n) {
		int d1 = n / 1000;
		int d234 = n % 1000;
		return (d234 * 10) + d1;
	}

	// R 명령어: n의 자릿수를 오른쪽으로 회전시킴
	public static int R(int n) {
		int d123 = n / 10;
		int d4 = n % 10;
		return (d4 * 1000) + d123;
	}
    
	static class RegisterState {
		int value;
		String operations;

		public RegisterState(int value, String operations) {
			this.value = value;
			this.operations = operations;
		}
	}

	private static String bfs(int a, int b) {
		boolean[] visited = new boolean[10000];
		Queue<RegisterState> queue = new LinkedList<>();
		queue.offer(new RegisterState(a, ""));
		visited[a] = true;

		while (!queue.isEmpty()) {
			RegisterState curr = queue.poll();

			if (curr.value == b) {
				return curr.operations;
			}

			// D 연산
			int dResult = D(curr.value);
			if (!visited[dResult]) {
				visited[dResult] = true;
				queue.offer(new RegisterState(dResult, curr.operations + "D"));
			}

			// S 연산
			int sResult = S(curr.value);
			if (!visited[sResult]) {
				visited[sResult] = true;
				queue.offer(new RegisterState(sResult, curr.operations + "S"));
			}

			// L 연산
			int lResult = L(curr.value);
			if (!visited[lResult]) {
				visited[lResult] = true;
				queue.offer(new RegisterState(lResult, curr.operations + "L"));
			}

			// R 연산
			int rResult = R(curr.value);
			if (!visited[rResult]) {
				visited[rResult] = true;
				queue.offer(new RegisterState(rResult, curr.operations + "R"));
			}
		}

		return ""; // 이론적으로 이곳에 도달하지 않음
	}
}