BOJ9019 DSLR

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

9019번: DSLR

처음에 시간초과가 났던 문제이다.

 

 첫시도 코드(통과는 함)

import java.io.*;
import java.util.*;
public class Main
{
    static int r;
    static int c;
    public static int DSLR(int number,int method){
        if(method==0){
            return (number*2)%10000;    
        }
        if(method==1){
            return number==0?9999:number-1;   
        }
        if(method==2){
            int first = number/1000;
            int second = (number%1000)/100;
            int third = (number%100)/10;
            int fourth = number%10;
            return second*1000 + third*100 + fourth*10 + first;
        }
        if(method==3){
            int first = number/1000;
            int second = (number%1000)/100;
            int third = (number%100)/10;
            int fourth = number%10;
            return fourth*1000 + first*100 + second*10 + third;
        }
        return 0;
    }

    
    public static String bfs(int a, int b){
        Queue<Node> q = new LinkedList();
        boolean[] visited = new boolean[10001];
        String[] move = {"D","S","L","R"};
        Node start = new Node(a,"");
        q.offer(start);
        while(q.size()>0){
            Node node = q.poll();
            if(node.number==b){
                return node.path;
            }
            visited[node.number] = true;
            for(int i=0; i<4;i++){
                Node next = new Node(DSLR(node.number,i),node.path+move[i]);
                if(!visited[next.number]){
                    q.offer(next);
 					//이 부분을 빼먹어서(잘못적어서) 시간초과가 났음;;
 					visited[next.number] = true;
                }
                
            }
        }
        return "";
    }
 
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int t= Integer.parseInt(br.readLine());
		
		while(t-->0){
		    String[] input1 = br.readLine().split(" ");
		    int a  = Integer.parseInt(input1[0]);
		    int b = Integer.parseInt(input1[1]);
            
            System.out.println(bfs(a,b));
            
		    
		    
		}
        
        
	}
	
	public static class Node{
	    int number;
	    String path;
	    public Node(int number, String path){
	        this.number =  number;
	        this.path = path;
	    }
	    
	}
	
	
	
}

 

 

인스턴스마다 경로를 들고 있는 것이 무겁다고 생각해

숫자범위만큼의 스트링 배열을 만들고 저장 시켜주었다.

import java.io.*;
import java.util.*;
public class Main
{
    public static int DSLR(int number,int method){
        if(method==0){
            return (number*2)%10000;    
        }
        if(method==1){
            return number==0?9999:number-1;   
        }
        if(method==2){
            int first = number/1000;
            int second = (number%1000)/100;
            int third = (number%100)/10;
            int fourth = number%10;
            return second*1000 + third*100 + fourth*10 + first;
        }
        if(method==3){
            int first = number/1000;
            int second = (number%1000)/100;
            int third = (number%100)/10;
            int fourth = number%10;
            return fourth*1000 + first*100 + second*10 + third;
        }
        return 0;
    }

    
    public static String bfs(int a, int b){
        Queue<Integer> q = new LinkedList();
        boolean[] visited = new boolean[10000];
        String[] route = new String[10000];
        String[] move = {"D","S","L","R"};
        q.offer(a);
        route[a]="";
        while(q.size()>0){
            int num = q.poll();
            if(num==b){
                return route[num];
            }
            visited[num] = true;
            for(int i=0; i<4;i++){
                int next = DSLR(num,i);
                if(!visited[next]){
                    q.offer(next);
                    visited[next] = true;
                    route[next] = route[num]+move[i];
                }
                
            }
        }
        return "";
    }
 
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int t= Integer.parseInt(br.readLine());
		
		while(t-->0){
		    String[] input1 = br.readLine().split(" ");
		    int a  = Integer.parseInt(input1[0]);
		    int b = Integer.parseInt(input1[1]);
            
            System.out.println(bfs(a,b));
            
		}
        
        
	}
	

	
	
	
}

 

 

예제 코드 (스트링 빌더 이용)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for (int t = 0; t < tc; t++) {
            int in = sc.nextInt();
            int out = sc.nextInt();
            boolean[] check = new boolean[10000];
            char[] cmd = {'D', 'S', 'L', 'R'};

            Queue<Register> q = new LinkedList<>();
            q.add(new Register(in, new StringBuilder()));
            check[in] = true;
                while (!q.isEmpty()) {
                    Register now = q.poll();
                    if (now.num == out) {
                        System.out.println(now.cmd);
                        break;
                    }
                    int[] next = {now.calcD(), now.calcS(), now.calcL(), now.calcR()};
                    for (int i = 0; i < 4; i++) {
                        if (!check[next[i]]) {
                            check[next[i]] = true;
                            q.add(new Register(next[i], new StringBuilder(now.cmd).append(cmd[i])));
                        }
                    }
                }

        }
    }
}

class Register {
    int num;
    StringBuilder cmd;
    Register(int num, StringBuilder cmd) {
        this.num = num;
        this.cmd = cmd;
    }
    public int calcD() {
        return (num * 2) % 10000;
    }
    public int calcS() {
        return (num - 1) < 0 ? 9999 : num - 1;
    }
    public int calcL() {
        return (num % 1000) * 10 + num / 1000;
    }
    public int calcR() {
        return (num % 10) * 1000 + num / 10;
    }
}