[Java] 백준 9019번 : DSLR*

문제

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

9019번: DSLR

 

 

풀이 과정

가능한 경로 중 가장 짧은 경로를 찾아야 하므로, BFS로 풀었다.

여기서 해당 경로 과정을 기록할 때는 Queue에 문자열을 넣어도되지만, 문자열을 합치는 비용이 크다.

따라서, 아래와 같이 해당 숫자의 index에 D, S, L, R중 어떤 명령어로 왔는지를 char형으로 저장해놓는다.

결과를 출력할 때는 parent배열을 따라 역으로 올라가면서, 경로를 합쳐준다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        while(T-- > 0){
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            sb.append(bfs(A, B)).append("\n");
        }
        System.out.println(sb);

    }

    public static String bfs(int A, int B){
        Queue<Integer> q = new LinkedList<>();
        int[] parent = new int[10_000];
        char[] process = new char[10_000];
        Arrays.fill(parent, -1);
        q.add(A);
        parent[A] = A;

        while(!q.isEmpty()){
            int now = q.poll();

            int next = (now<<1)%10000;
            if(parent[next] == -1){
                parent[next] = now;
                process[next] = 'D';
                q.add(next);
            }
            next = (now+9999)%10000;
            if(parent[next] == -1){
                parent[next] = now;
                process[next] = 'S';
                q.add(next);
            }
            next = now/1000 + now%1000*10;
            if(parent[next] == -1){
                parent[next] = now;
                process[next] = 'L';
                q.add(next);
            }
            next = now/10 + now%10*1000;
            if(parent[next] == -1){
                parent[next] = now;
                process[next] = 'R';
                q.add(next);
            }

            if(parent[B]!=-1){
                break;
            }
        }

        StringBuilder sb = new StringBuilder();
        while(A!=B){
            sb.append(process[B]);
            B = parent[B];
        }
        return sb.reverse().toString();
    }
}

 

 

결과