Baekjoon - 9019

문제

Solved.ac Class3++

1차시도

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int size = Integer.parseInt(br.readLine());
		for (int i = 0; i < size; i++) {
			String[] split = br.readLine().split(" ");
			int numA = Integer.parseInt(split[0]);
			int numB = Integer.parseInt(split[1]);
			sb.append(solve(numA, numB)).append("\n");
		}
		System.out.println(sb);
	}

	private static String solve(int numA, int target) {
		Queue<Integer> queue = new LinkedList<>();
		boolean[] isVisit = new boolean[10000];
		String[] commands = new String[10000];

		queue.add(numA);
		isVisit[numA] = true;
		commands[numA] = "";

		while (!queue.isEmpty() && !isVisit[target]) {
			int now = queue.remove();

			int d = functionD(now);
			int s = functionS(now);
			int l = functionL(now);
			int r = functionR(now);

			if (!isVisit[d]) {
				queue.add(d);
				isVisit[d] = true;
				commands[d] = commands[now] + "D";
			}
			if (!isVisit[s]) {
				queue.add(s);
				isVisit[s] = true;
				commands[s] = commands[now] + "S";
			}
			if (!isVisit[l]) {
				queue.add(l);
				isVisit[l] = true;
				commands[l] = commands[now] + "L";
			}
			if (!isVisit[r]) {
				queue.add(r);
				isVisit[r] = true;
				commands[r] = commands[now] + "R";
			}

		}

		return commands[target];
	}

	private static int functionD(int num) {
		return (num * 2) % 10000;
	}

	private static int functionS(int num) {
		return num == 0 ? 9999 : num - 1;
	}

	private static int functionL(int num) {
		return ((num % 1000) * 10) + (num / 1000);
	}

	private static int functionR(int num) {
		return (num / 10) + ((num % 10) * 1000);
	}

}

전체를 돌면서, 시도해본다.
저장을 어차피 10000 안에 끝나니까 배열을 만들어서 해결한다.

성공

BFS는
최단경로 찾기, 레벨 순회에 자주 쓰인다.
명령어의 최소를 찾아야 하니 최단 경로 찾기로 볼 수 있겠다.

ToKotlin

fun main() {
    val size = readln().toInt()
    val sb = StringBuilder()

    for (i in 0..<size) {
        val data = readln().split(" ")
        sb.append(solve(data[0].toInt(), data[1].toInt())).append("\n")
    }
    print(sb)
}

private fun solve(numA: Int, target: Int): String {
    val queue: Queue<Int> = LinkedList()
    val isVisit = BooleanArray(10000)
    val commands = arrayOfNulls<String>(10000)

    queue.add(numA)
    isVisit[numA] = true
    commands[numA] = ""

    while (!queue.isEmpty() && !isVisit[target]) {
        val now = queue.remove()

        val d = functionD(now)
        val s = functionS(now)
        val l = functionL(now)
        val r = functionR(now)

        if (!isVisit[d]) {
            queue.add(d)
            isVisit[d] = true
            commands[d] = commands[now] + "D"
        }
        if (!isVisit[s]) {
            queue.add(s)
            isVisit[s] = true
            commands[s] = commands[now] + "S"
        }
        if (!isVisit[l]) {
            queue.add(l)
            isVisit[l] = true
            commands[l] = commands[now] + "L"
        }
        if (!isVisit[r]) {
            queue.add(r)
            isVisit[r] = true
            commands[r] = commands[now] + "R"
        }
    }

    return commands[target]!!
}

private fun functionD(num: Int): Int = (num * 2) % 10000

private fun functionS(num: Int): Int = if (num==0) 9999 else num - 1

private fun functionL(num: Int): Int = ((num % 1000) * 10) + (num / 1000)

private fun functionR(num: Int): Int = (num / 10) + ((num % 10) * 1000)