P9019. DSLR

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

9019번: DSLR

설명

하나의 경우를 깊이있게 들어가기보다 주변을 탐색하는 BFS 기법을 이용해서 문제를 풀이한다.

visit 배열을 생성하고, 방문한 값들은 true로 변경한다.

 

D연산

num을 2배 했을 때 9999보다 크면, %10000을 하는 것과 9999 이하일 때 %10000하는 것은 같다. 

=> num * 2 % 10000

 

S연산

n == 0이면, 9999를 반환한다.

=> n == 0 ? 9999 : n-1

 

L연산

1000 자리 숫자를 1의 자리 숫자로 내리고, 나머지 숫자들은 *10한다.

=> n % 1000 * 10 + n / 1000

 

R연산

1의 자리 숫자를 1000의 자리 숫자로 올리고, 나머지 숫자들을 /10 한다.

=> n % 10 * 1000 + n / 10

 

코드

BFS

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

public class Main {
    static int T;
    static int A, B;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        T = Integer.parseInt(br.readLine());
        
        for(int i = 0; i < T; i++) {
        	String[] str = br.readLine().split(" ");
            A = Integer.parseInt(str[0]);
            B = Integer.parseInt(str[1]);
            
            boolean[] visit = new boolean[10000];
            visit[A] = true;
            Queue<Register> queue = new LinkedList<>();
            queue.add(new Register(A, ""));	// 시작점
            
            while(!queue.isEmpty()) {
            	Register cur = queue.poll();
                
                if(cur.num == B) {
                	sb.append(cur.command).append("\n");
                    break;
                }
                if(!visit[cur.D()]) {
                	queue.add(new Register(cur.D(), cur.command + "D"));
                    visit[cur.D()] = true;
                }
                if(!visit[cur.S()]) {
                	queue.add(new Register(cur.S(), cur.command + "S"));
                    visit[cur.S()] = true;
                }
                if(!visit[cur.L()]) {
                	queue.add(new Register(cur.L(), cur.command + "L"));
                    visit[cur.L()] = true;
                }
                if(!visit[cur.R()]) {
                	queue.add(new Register(cur.R(), cur.command + "R"));
                    visit[cur.R()] = true;
				}
			}              
		}
        System.out.println(sb);
	}
}    
 
class Register {
	int num;
    String command;
    
    public Register(int num, String command) {
    	this.num = num;
        this.command = command;
	}
    
    int D() {
    	return (num * 2) % 10000;
	}
    
    int S() {
    	return num == 0 ? 9999 : num - 1;
	}
    
    int L() {
    	return num % 1000 * 10 + num / 1000;
	}
    
    int R() {
    	return num % 10 * 1000 + num / 10;
	}
}

 

Reference 

https://girawhale.tistory.com/15