백준 9010번: DSLR [BFS][탐색] -Java

 

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

9019번: DSLR

 

 

<Java 코드>

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		
		for (int tc = 0; tc < T; tc++) {
			st=new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			
			Queue<Num> q = new LinkedList<Num>();
			q.add(new Num(A,new StringBuilder()));
			boolean visit[] = new boolean[10001];
			
			
			while(!q.isEmpty()) {
				
				Num n = q.poll();
				
				if(n.num==B) {
					System.out.println(n.str);
					break;
				}
				
				int calc[] = {n.num*2 > 9999? (n.num*2) %10000 : n.num*2
						, n.num-1 <0 ? 9999 : n.num-1
						, ((n.num%1000)*10)+(n.num/1000)
						, (n.num/10)+(n.num%10)*1000};
				
				char dslr[] = {'D','S','L','R'};
				
				for (int i = 0; i < 4; i++) {
					if(visit[calc[i]])
						continue;
					
					visit[calc[i]] = true;
					StringBuilder sb = new StringBuilder(n.str);
					q.add(new Num(calc[i],sb.append(dslr[i])));
					
				}
				
			}
			
			
			
		}
	}
	
	static class Num{
		int num;
		StringBuilder str;
		
		public Num(int n,StringBuilder s) {
			this.num = n;
			this.str =s;
		}
	}

}