[ Algorithm ] 백준 9019번 : DSLR - [JAVA]

Minsu Lee·2023년 4월 12일

Java algorithm

baekjoon

목록 보기

2/16

🎆백준 9019번 DSLR🎆

📌문제

🔍문제 설명

문제 링크 : https://www.acmicpc.net/problem/9019

🔍예제 입력

3
1234 3412
1000 1
1 16

🔍예제 출력

LL
L
DDDD

📌풀이

🔍풀이 설명

BFS 그래프 탐색을 이용한 문제였다. 현재 숫자에서 D, S, L, R 각각의 계산을 진행한 수를 탐색해 나가는 알고리즘을 작성하였다.

💡 생각해보기

출력을 개행 포함해서 하였는지

S 연산 수행시에, n == 0 일 때 9999를 return 했는지

123을 L연산 수행시 231이 아니라, 1230이 되게 했는지,
마찬가지로 123을 R연산 수행시 312가 아니라 3012가 되게 했는지

방문 체크 배열을 혹시 전역으로 설정했는지

처음 방문한 위치(A)를 visited[a] = true로 설정했는지

while (!queue.isEmpty() && !visited[B]){
            int current = queue.poll();

            //D, S, L, R 계산된 4개 수 저장
            int[] DSLR = {(current*2) % 10000, current == 0 ? 9999 : current - 1,
                    (current%1000)*10 + current/1000, current/10 + (current%10)*1000};

            String[] dslr = {"D", "S", "L", "R"};
            for(int j=0; j<DSLR.length; j++) {
                int n = DSLR[j];
                //방문 체크 후, 큐에 넣어줌
                if(!visited[n]) {
                    queue.add(n);
                    visited[n] = true;
                    count[n] = count[current] + dslr[j];
                }
            }
        }

반복문으로 DSLR 계산되는 수를 검사했는데 지금 다시 생각해보니까 DSLR은 4가지 계산밖에 없으니까 조건문으로 구현했으면 수행시간을 단축할 수 있겠다는 생각을 했다..!

🔍코드

package Graph;

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

//DSLR
public class p9019 {
    static String BFS(int A, int B) {
        boolean []visited = new boolean[10000];
        String count[] = new String[10000];
        Queue<Integer> queue = new LinkedList<>();
        Arrays.fill(count,  "");

        queue.add(A);
        count[A] = "";
        visited[A] = true;
        while (!queue.isEmpty() && !visited[B]){
            int current = queue.poll();

            //D, S, L, R 계산된 4개 수 저장
            int[] DSLR = {(current*2) % 10000, current == 0 ? 9999 : current - 1,
                    (current%1000)*10 + current/1000, current/10 + (current%10)*1000};

            String[] dslr = {"D", "S", "L", "R"};
            for(int j=0; j<DSLR.length; j++) {
                int n = DSLR[j];
                //방문 체크 후, 큐에 넣어줌
                if(!visited[n]) {
                    queue.add(n);
                    visited[n] = true;
                    count[n] = count[current] + dslr[j];
                }
            }
        }
    return count[B];
}
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        int A, B;
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
            BFS(A, B);
            System.out.println(BFS(A, B));
        }
    }
}