백준9019_DSLR

생각보다 별거 없었다.

DSLR가져오는 아이디어만 고려하면 나머지는 그냥 기본 BFS로 접근하면 완성,.

아래와 같이 만들었다.

어차피 9999까지 만들고 visited 배열 있으니까 시간복잡도에 무리는 없을 것 같았다.

물론 test case가 많지만.

 

- 참고 사항으로는 그냥 초기화만 해줬는데- 

그렇게 되면 String 배열에서는 null값이 들어간다는 것을 알았지만서도 (이전것 + " ")를 통해서 graph 배열에 넣어주니까 예상과는 다르게

NullDSLR 이런식으로 들어갔다. 그래서 start 배열에는 그냥 "" <- 빈 string을 넣어서 해결할 수 있었다.

 

아래 - 

 

public static int[] makeDSLR(int now) {
        return new int[] {

(now * 2) % 10000,

 (now == 0)? 9999: now-1,

 now / 1000 + (now % 1000) * 10,

 now / 10 + (now % 10 * 1000)};
    }

 

package programers;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class BOJ9019_DSLR {
    static String[] graph;
    static boolean[] visited;
    static int start;
    static int end;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i =0; i < n; i++) {
            start = sc.nextInt();
            end = sc.nextInt();
            graph = new String[10000];
            visited = new boolean[10000];
            bfs();
            System.out.println(graph[end]);
        }
    }
    public static void bfs() {
        Queue<Integer> q = new ArrayDeque<>();
        q.add(start);
        graph[start] = "";
        visited[start] = true;
        while(!q.isEmpty()) {
            int now = q.poll();
            if (now == end) {
                break;
            }
            int[] dslr = makeDSLR(now);
            for(int i= 0; i < dslr.length; i++) {
                if(!visited[dslr[i]]) {
                    visited[dslr[i]]= true;
                    q.add(dslr[i]);
                    if(i == 0) {
                        graph[dslr[i]] = graph[now] + "D";
                    } else if(i == 1) {
                        graph[dslr[i]] = graph[now] + "S";
                    }  else if(i == 2) {
                        graph[dslr[i]] = graph[now] + "L";
                    } else {
                        graph[dslr[i]] = graph[now] + "R";
                    }
                }
            }

        }
    }
    public static int[] makeDSLR(int now) {
        return new int[] {(now * 2) % 10000, (now == 0)? 9999: now-1, now / 1000 + (now % 1000) * 10, now / 10 + (now % 10 * 1000)};
    }
}