백준 9019번 : DSLR [Java]

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

문제 탐색하기

비교적 구현이 쉬운 BFS 문제인거 같다. 각 연산을 구현하여 최소 명령어를 구하면 된다. 이 때 BFS 탈출 조건은 더 이상 방문 할 곳이 없을 때 생각해보아야 하는데 시간 제한이 6초로 비교적 넉넉한 것을 보면 연산이 오래 걸리지 않나 생각된다. 이에 따라서 자리 수의 최소인 0부터 9999 까지 방문 할 수 있도록 배열을 구성하고 이에 맞추어 BFS를 구현하면 정답을 받을 수 있을 것 같다.

 

방법만 떠올리면 빠르게 구현할 수 있는 문제이다. 각 연산은 설명이 어렵게 되어 있지만 잘만 생각해보면 사칙연산에 모듈러만 있으면 구현할 수 있다. 각 연산은 아래 처럼 구현할 수 있다.

• D : 두배를 하고 9999를 넘는 수가 나오면 10000으로 나눈 나머지를 택한다. 이외의 경우에는 두배를 곱한 것을 반환한다.
• S : 1을 빼고 0보다 작으면 9999 이외의 경우에는 1을 뺀 수를 반환한다.
• L : 1000으로 나눈 나머지에 10을 곱한 것과 1000으로 나눈 몫을 더한다.
• R : 10으로 나눈 몫 과 10으로 나눈 나머지에 1000을 곱한 값을 더한다.

코드 구현하기

1. 입력을 처리한 후 반복문을 통해 각 테스트 케이스를 처리한다.
   1. 2차원 배열을 설정하여 0 ~ 9999번 인덱스를 방문할 수 있도록 구현한다
   2. 앞서 문제 탐색하기에서 주어진 대로 d, s, l, r에 해당하는 각 연산을 구현한다.
   3. 각 연산에 대해서 방문 체크를 하고 큐에 더한다.
2. 모든 테스트 케이스를 처리하면 한번에 답을 출력한다.

풀이

import java.io.*;
import java.util.*;

public class Main {
	static int TC, A, B, count = Integer.MAX_VALUE;
	static StringBuilder answer = new StringBuilder();

	public static void main(String[] args) {
		FastReader sc = new FastReader();
		TC = sc.nextInt();
		for (int i = 0; i < TC; i++) {
			A = sc.nextInt();
			B = sc.nextInt();
			bfs(A, B, "");
		}
		System.out.println(answer);
	}

	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

	}

	static class Node {
		int now;
		String s;

		public Node(int now, String s) {
			this.now = now;
			this.s = s;
		}
	}

	static void bfs(int cur, int target, String str) {
		boolean[] visited = new boolean[10000];
		String[] values = new String[10000];
		LinkedList<Node> q = new LinkedList<>();
		q.add(new Node(cur, str));
		visited[cur] = true;
		while (!q.isEmpty()) {
			Node n = q.poll();

			int d = n.now * 2 > 9999 ? n.now * 2 % 10000 : n.now * 2;
			int s = n.now - 1 < 0 ? 9999 : n.now - 1;
			int l = n.now % 1000 * 10 + n.now / 1000;
			int r = n.now / 10 + n.now % 10 * 1000;
			
			if (!visited[d]) {
				visited[d] = true;
				values[d] = n.s + "D";
				q.add(new Node(d, n.s + "D"));
			}

			if (!visited[s]) {
				visited[s] = true;
				values[s] = n.s + "S";
				q.add(new Node(s, n.s + "S"));
			}

			if (!visited[l]) {
				visited[l] = true;
				values[l] = n.s + "L";
				q.add(new Node(l, n.s + "L"));
			}

			if (!visited[r]) {
				visited[r] = true;
				values[r] = n.s + "R";
				q.add(new Node(r, n.s + "R"));
			}
		}

		answer.append(values[target]).append("\n");
	}
}