[백준 9019번 / Java] DSLR - BFS

문제 링크

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

9019번: DSLR

 

 

---

 

 

풀이

엄청난 삽질을 했던 문제

 

한번에 풀겠거니 했는데 처음에는 메모리 초과가 발생했는데, 이유는 아마 String 배열 하나로 풀었기 때문인 것 같다.

어떻게 boolean 배열 없이 단순 String 배열로만 풀어보자 하고 고집하다가 계속 오답을 발생시켰다.

 

추가로, l과 r을 계산하는 조건을 구할 때, 처음에 String으로 받아서 charAt로 풀었기 때문에 메모리가 폭팔했다.

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

public class BaekJoon9019 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int before = Integer.parseInt(st.nextToken());
            int after = Integer.parseInt(st.nextToken());

            String[] tmp = new String[10000];
            boolean[] bl = new boolean[10000];
            Queue<Integer> queue = new LinkedList<>();

            Arrays.fill(tmp, "");
            queue.add(before);
            bl[before] = true;

            System.out.println(bfs(queue, tmp, after, bl));
        }

    }

    private static String bfs(Queue<Integer> queue, String[] tmp, int after, boolean[] bl) {
        while(!queue.isEmpty()) {
            int number = queue.poll();

            if(number == after) return tmp[number];

            int d = (number * 2) % 10000;
            int s = number == 0 ? 9999 : number - 1;
            int l = (number % 1000) * 10 + (number / 1000);
            int r = (number % 10) * 1000 + (number / 10);

            if(!bl[d]) {
                tmp[d] = tmp[number] + "D";
                queue.add(d);
                bl[d] = true;
            }
            if(!bl[s]) {
                tmp[s] = tmp[number] + "S";
                queue.add(s);
                bl[s] = true;
            }
            if(!bl[l]) {
                tmp[l] = tmp[number] + "L";
                queue.add(l);
                bl[l] = true;
            }
            if(!bl[r]) {
                tmp[r] = tmp[number] + "R";
                queue.add(r);
                bl[r] = true;
            }

        }
        return "";
    }
}