[JAVA] 백준 - DSLR 9019 ( BFS)

www.acmicpc.net/problem/9019

9019번: DSLR

 클래스 Pair 를 계속 생성해서 그런지 모르겠는데 메모리 엄청 쓴다..

 

쓰지 않으면 더 빠르게 구동 되지만 직관적으로 이해하고 문제 풀이가 빨라서 Pair 클래스를 만들어서 쓰고 있다.

 

# 문제의 관건인 D S L R 을 구현하기

 

            //D
            nx = (x*2)%10000;

            //S
            nx = x==0?9999:x-1;

            //L
            nx = (x%1000)*10 + (x/1000);

            //R
            nx = (x/10) + 1000*(x%10);

 

# BFS 로 방문체크 하면서 최소 길이의 문자열 반환하기

 

import java.util.LinkedList;
import java.util.*;
class Main{

    static int testCase;
    static int st,ed;
    static boolean[] visited; // 0 ~ 9999

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        testCase = sc.nextInt();
        while(testCase>0){
            st = sc.nextInt();
            ed = sc.nextInt();
            System.out.println(solve());
            testCase--;
        }

    }

    public static String solve(){
        visited = new boolean[10000];
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(st,""));
        visited[st] = true;
        String ret= "";
        boolean flag = false;
        while(!q.isEmpty()){
            Pair p = q.poll();

            int x = p.x;
            String s = p.s;

            if(x == ed){
                if(!flag) {ret = s;flag=true;}
                else {
                    if(ret.length() > s.length()){
                        ret = s;
                    }
                }
            }

            int nx;
            //D
            nx = (x*2)%10000;
            if(!visited[nx]) {
                visited[nx] = true;
                q.add(new Pair(nx,s+"D"));
            }
            //S
            nx = x==0?9999:x-1;
            if(!visited[nx]) {
                visited[nx] = true;
                q.add(new Pair(nx,s+"S"));
            }
            //L
            nx = (x%1000)*10 + (x/1000);
            if(!visited[nx]){
                visited[nx] = true;
                q.add(new Pair(nx,s+"L"));
            }
            //R
            nx = (x/10) + 1000*(x%10);
            if(!visited[nx]) {
                visited[nx] = true;
                q.add(new Pair(nx,s+"R"));
            }
        }
        return ret;
    }

    static class Pair{
        int x;
        String s;

        public Pair(int x,String s){
            this.x = x;
            this.s = s;
        }
    }

}