[백준/Java] 9019 - DSLR

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

문제

---

풀이

문제에서 최소, 최단이라는 단어가 나오면 우선 BFS를 떠올려야 한다

현재 숫자에서 모든 D, S, L, R 명령을 거친 후의 숫자를 구하고 그 숫자를 시작으로 또 명령을 거치는 것이다

이때 큐에 (숫자, 현재까지 명령어) 쌍을 넣어야 하는데 `Pair`라는 클래스를 따로 선언해주었다

// (숫자, 명령어) 쌍
class Pair {
	int num;
	String cmd;

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

그래서 큐에 넣을 때 현재까지 명령어에 각 명령어를 덧붙이는 형태로 추가하였다

루프를 도는 중에 최종 숫자와 같아지면 현재까지 명령어를 출력하면 된다

 

주의할 점은 왼쪽 회전과 오른쪽 회전이다

처음에는 예를 들어 35가 있다고 하면, L을 수행 -> 53 인줄 알았다

근데 4자리 수라고 가정하는 것이었다

35면 0035, L 수행 -> 0350 이 되는 것이다

R의 경우도 똑같다

201(0201) -> R 수행 -> 1020

이 점을 주의해서 L, R 숫자를 구해야 한다

 

자세한 건 코드를 보자

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

// (숫자, 명령어) 쌍
class Pair {
	int num;
	String cmd;

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

public class Main {


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


		int T = Integer.parseInt(br.readLine());
		while (T-- > 0) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());

			bfs(A, B);
		}

		br.close();
	}

	static void bfs(int A, int B) {
		boolean[] visited = new boolean[10000]; // 방문 처리 배열
		Queue<Pair> queue = new LinkedList<>();

		visited[A] = true; // 초기 숫자 A를 방문 처리
		queue.add(new Pair(A, "")); // 큐에 숫자와 명령어 쌍을 넣어준다

		while (!queue.isEmpty()) {
			Pair current = queue.poll(); // 현재 쌍을 꺼낸다
			int curNum = current.num; // 현재 숫자
			String curCmd = current.cmd; // 현재까지 명령어

			// 현재 숫자와 B가 같으면 현재까지 명령어를 출력한다
			if (curNum == B) {
				System.out.println(curCmd);
				return;
			}

			// 각 명령어에 맞는 숫자를 구해준다
			int nextNumD = (curNum * 2) % 10000; // 2배
			int nextNumS = (curNum - 1 >= 0) ? curNum - 1 : 9999; // -1
			int nextNumL = (curNum % 1000) * 10 + curNum / 1000; // 왼쪽 이동
			int nextNumR = (curNum % 10) * 1000 + curNum / 10; // 오른쪽 이동

			// 각 숫자를 방문하지 않았으면 수행
			// 방문처리를 하고
			// (해당 숫자, 현재까지 명령어에 각 명령어를 더한 문자열)을 큐에 넣어준다
			if (!visited[nextNumD]) {
				visited[nextNumD] = true;
				queue.add(new Pair(nextNumD, curCmd + "D"));
			}
			if (!visited[nextNumS]) {
				visited[nextNumS] = true;
				queue.add(new Pair(nextNumS, curCmd + "S"));
			}
			if (!visited[nextNumL]) {
				visited[nextNumL] = true;
				queue.add(new Pair(nextNumL, curCmd + "L"));
			}
			if (!visited[nextNumR]) {
				visited[nextNumR] = true;
				queue.add(new Pair(nextNumR, curCmd + "R"));
			}
		}
	}
}

결과