DSLR [백준 9019][JAVA][골드5][String][BFS]

 

[광고 누르면 오늘의 행운 상승!!]

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

9019번: DSLR

1. 참고사항

- 10000개의 VISIT 배열을 통해 이미 지나간 숫자면 continue;

2. 구현

- D,S,L,R,에 해당하는 로직을 실행한다
- D : 숫자를 2배로 한다. 
- S : 숫자에 -1을 더한다.
- L : 숫자를 왼쪽으로 한칸 민다. (나눗셈과 나머지 연산 사용)
- R : 숫자를 오른쪽으로 한칸 민다. (나눗셈과 나머지 연산 사용)

- 결과 숫자가 목적 숫자와 같으면 return
- 결과 숫자가 이미 나온 숫자면 return
- 모두 아니라면 숫자를 q에넣고 다시 bfs를 돌린다.
- 반복

package Study8;

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

public class DSLR {
	static class Calc{
		int n;
		String s;
		public Calc(int n, String s) {
			this.n = n;
			this.s = s;
		}
	}
	static int T,ans;
	static int A,B;
	static boolean visit[];
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		T = Integer.parseInt(st.nextToken());
		
		for (int tc = 0; tc < T; tc++) {
			st = new StringTokenizer(br.readLine());
			A = Integer.parseInt(st.nextToken());
			B = Integer.parseInt(st.nextToken());
			
			visit = new boolean[10000];
			bfs();
		}
	}
	private static void bfs() {
		Queue<Calc> q = new LinkedList<>();
		q.add(new Calc(A, ""));
		visit[A] = true;
		
		while(!q.isEmpty()) {
			Calc calc = q.poll();
			
			for (int i = 0; i < 4; i++) {
				int cur = calc.n;
				int num =0;
				int tmp, n;
				char c = 0;
				switch(i) {
					case 0:{ 
						cur *=2;
						if(cur > 9999) cur%=10000;
						c = 'D';
						break;
					}
					case 1:{
						if(cur == 0) cur = 9999;
						else         cur -=1;
						c = 'S';
						break;
					}
					case 2:{
						n = cur / 1000;
						tmp = cur % 1000;
						num = tmp*10 + n;
						cur = num;
						c = 'L';
						break;
					}
					case 3:{
						n = cur % 10;
						tmp = cur / 10;
						num = tmp + n * 1000;
						cur = num;
						c = 'R';
						break;
					}
				}
				
				if(cur == B) {
					System.out.println(calc.s+c);
					return;
				}
				
				if(visit[cur]) continue;
				visit[cur] = true;
				q.add(new Calc(cur, calc.s+c));
			}
		}
		
	}

}