[Algorithm/Java] 백준 9019번 - DSLR
https://www.acmicpc.net/problem/9019
📌 문제
문제 유형
- 그래프
문제 설명
D, S, L, R 명령을 했을 때 A -> B가 되는 최소 명령을 찾는 문제
- D는 a을 두 배로
- 9999보다 크면 10000으로 나눈 나머지 저장
- S는 a-1을 저장
- a가 0보다 크면 9999 저장
- L은 각 자리수 왼쪽으로 회전
- d2, d3, d4, d1
- R은 각 자리수 오른쪽으로 회전
- d4, d1, d2, d3
입력
- 프로그램 입력은 T 개의 테스트 케이스로 구성된다.
- 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다.
- 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다.
- A 와 B는 모두 0 이상 10,000 미만이다.
3
1234 3412
1000 1
1 16
출력
- A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다.
- 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.
LL
L
DDDD
🔍 문제 풀이
(숫자 상태, 연산 문자열)
을 담는 Pair 클래스 생성- 시작 숫자를 Pair로 만들어 큐에 넣고 방문 처리
- 큐에서 하나씩 꺼내며 D, S, L, R 연산 수행
- 연산 결과가 방문하지 않은 숫자라면 큐에 추가
- 목표 숫자에 도달하면 해당 Pair의 연산 문자열을 반환
📌 놓친 점
클래스 생성
자바의 큐는 기본적으로 하나의 타입만 저장할 수 있으므로, 숫자 상태와 연산 문자열을 함께 저장하려면 사용자 정의 클래스가 필요하다.
Python의 튜플과 비슷한 개념이다.
BFS를 하면서 두 가지 정보를 같이 저장해야 하기 때문에, num과 ops를 한 번에 저장하는 클래스 Pair
를 만든다.
static class Pair {
int num; // 현재 숫자
String ops; // 지금까지 연산 문자열
// 생성자
public Pair(int num, String ops) {
this.num = num;
this.ops = ops;
}
}
아래와 같이 사용 가능하다.
Pair p = new Pair(1234, "DS");
System.out.println(p.num); // 1234
System.out.println(p.ops); // DS
- 생성자(Constructor) 란?
→ new Pair(1234, "DS")
처럼 객체를 만들 때 자동으로 값을 저장해주는 역할this.num = num
: 왼쪽은 클래스 안의 변수, 오른쪽 num은 매개변수- 즉, 값을 클래스 안에 저장해주는 함수
L연산과 R 공식
L과 R 연산은 숫자의 자리수를 회전시키는 연산이다.
예를 들어 1000에 대해 연산을 적용하면 다음과 같은 결과가 나온다.
1000 → L → 0001
-> 자바에서는 앞의 0이 생략되어 실제 값은 11000 → R → 0100
-> 실제 값은 100
자바에서는 정수형 앞에 오는 0을 생략하기 때문에,
연산 결과를 출력할 때 자릿수가 줄어든 것처럼 보일 수 있다.
하지만 연산 자체는 정확히 작동하지만, 결과 출력 시 혼동하지 않도록 하자!
연산 | 의미 |
---|---|
L | 숫자를 왼쪽으로 회전 (1234 → 2341) |
R | 숫자를 오른쪽으로 회전 (1234 → 4123) |
L 연산 구현
int l = (n % 1000) * 10 + (n / 1000);
- 뒤 3자리를 왼쪽으로 밀고
- 맨 앞 자리를 맨 뒤에 붙임
R 연산
int r = (n % 10) * 1000 + (n / 10);
- 맨 끝 자리를 맨 앞으로 보내고
- 나머지 3자리는 한 칸 뒤로 밀기
💻 전체 코드
import java.io.*;
import java.util.*;
public class Main {
static class Pair{
int num;
String ops;
public Pair(int num, String ops){
this.num = num;
this.ops = ops;
}
}
public static String bfs(int start, int target) {
boolean[] visited = new boolean[10_000];
Deque<Pair> dq = new ArrayDeque<>();
dq.offer(new Pair(start, ""));
visited[start] = true;
while(!dq.isEmpty()){
Pair cur = dq.poll();
if(cur.num == target) return cur.ops;
// D
int d = (cur.num * 2) % 10_000;
if(!visited[d]){
visited[d] = true;
dq.offer(new Pair(d, cur.ops + "D"));
}
// S
int s = (cur.num == 0) ? 9999 : cur.num - 1;
if(!visited[s]){
visited[s] = true;
dq.offer(new Pair(s, cur.ops + "S"));
}
// L
int l = (cur.num % 1000) * 10 + cur.num / 1000;
if (!visited[l]) {
visited[l] = true;
dq.offer(new Pair(l, cur.ops + "L"));
}
// R
int r = (cur.num % 10) * 1000 + cur.num / 10;
if (!visited[r]) {
visited[r] = true;
dq.offer(new Pair(r, cur.ops + "R"));
}
}
return "";
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while(t --> 0){
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
System.out.println(bfs(a,b));
}
}
}
댓글남기기