백준 9019번 - DSLR (Java, BFS 풀이)

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

 

문제 설명

네 자리 수 A를 네 가지 명령어(D, S, L, R)를 사용하여 B로 바꾸는 가장 짧은 명령어 문자열을 구하는 문제입니다.

• D: n을 두 배로 만들고 10000으로 나눈 나머지
• S: n에서 1을 뺌 (0이면 9999)
• L: n을 왼쪽으로 한 자리 회전 (1234 → 2341)
• R: n을 오른쪽으로 한 자리 회전 (1234 → 4123)

---

전체 코드

import java.util.*;

public class Main {	
	static class Pair {
		int num;
		String commands;
	
		Pair(int num, String commands) {
			this.num = num;
			this.commands = commands;
		}
	}
	
	static void BFS(int start, int target) {
		boolean[] visited = new boolean[10000];
		Queue<Pair> q = new LinkedList<>();
		q.offer(new Pair(start, ""));
		visited[start] = true;
		
		while(!q.isEmpty()) {
			Pair current = q.poll();
			int num = current.num;
			String commands = current.commands;
			
			if(num == target) {
				System.out.println(commands); // 결과 출력
				return;
			}
			
			int D = (num * 2) % 10000;
			int S = (num == 0) ? 9999 : num - 1;
			int L = (num % 1000) * 10 + num / 1000;
			int R = (num % 10) * 1000 + num / 10;
			
			if (!visited[D]) {
				visited[D] = true;
				q.offer(new Pair(D, commands + "D"));
			}
			if (!visited[S]) {
				visited[S] = true;
				q.offer(new Pair(S, commands + "S"));
			}
			if (!visited[L]) {
				visited[L] = true;
				q.offer(new Pair(L, commands + "L"));
			}
			if (!visited[R]) {
				visited[R] = true;
				q.offer(new Pair(R, commands + "R"));
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		for (int i = 0; i < n; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			BFS(a, b);
		}
		
		sc.close();
	}
}

---

코드 설명

1. Pair 클래스

• 현재 숫자와 그 숫자에 도달하기까지 사용한 명령어 문자열을 저장합니다.

2. BFS() 함수

• 큐를 이용해 너비 우선 탐색을 수행합니다.
• visited[10000] 배열을 사용해 중복 방문을 방지합니다.
• 각 명령어(D, S, L, R)를 수행한 결과를 큐에 추가합니다.

3. 명령어 처리

• D (Double)
  → (num * 2) % 10000
• S (Subtract)
  → num == 0 ? 9999 : num - 1
• L (Left rotate)
  → ((num % 1000) * 10 + num / 1000)
• R (Right rotate)
  → ((num % 10) * 1000 + num / 10)

4. 종료 조건

• 큐에서 꺼낸 숫자가 목표 숫자 target과 같으면 결과 문자열 출력 후 종료

---

시간 복잡도 분석

• 가능한 숫자는 0부터 9999까지 총 10000개입니다.
• 각 숫자에서 가능한 연산은 4개(D, S, L, R)입니다.
• BFS로 각 상태를 한 번씩만 방문하므로 전체 시간 복잡도는 O(10000)