알고리즘 풀이 - 백준 9019(DSLR, 그래프(BFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

D, S, L, R이라는 명령어를 통해 숫자를 연산하는 계산기가 있을 때, A라는 숫자를 B로 만들기 위해 최소 연산을 수행하는 경우를 출력하는 문제

 

 

2. 풀이

 

이 문제는 전형적인 BFS 문제로 각 명령어를 통해 구한 숫자들을 탐색하고 원하는 숫자가 나올 때까지 그것을 반복하는 문제이다. 명령들은 다음과 같다.

① D : x2를 하고 10000으로 나눈 나머지를 구한다.
② S : -1을 더하되 0이된 경우 9999를 입력한다.
③ L : 좌측으로 한 칸씩 이동
④ R : 우측으로 한 칸씩 이동

이 문제는 모든 숫자가 4자리수로 고정이라는 부분에 있다.

예를 들어 1이라면 0001이라고 생각하면 된다. 이 부분을 간과하고 풀면 예를 들어 10을 L 명령어로 이동 시, 1이라고 오해할 수 있다.

무조건 4자리이므로 10을 L명령어를 하면 100이 되는 것이다. 이 부분을 제대로 이해하지 못하여서 코드가 길어졌고 시간만 많이 쓰게 되었다.

 

D, S 명령은 간단히 구할 수 있다. L, R에 대해서 알아보면 다음과 같다.

L 명령어 : 1000으로 나눈 나머지에 10을 곱하고 원래 수를 1000으로 나눈 몫을 더한다.
예) 5642를 L 명령어 시
  → (5642 % 1000) x 10 + (5642 / 1000) = 642 x 10 + 5 = 6425

R 명령어 : 10으로 나눈 나머지에 1000을 곱한 수에 원래 수를 10으로 나눈 몫을 더한다.
예) 6425를 R 명령어 시
  → (6425 % 10) x 1000 + (6425 / 10) = 5 x 1000 + 642 = 5642

 

위와 같은 방식을 이용해 BFS를 수행하면 답을 구할 수 있다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        StringTokenizer st = null;
        StringBuilder sb = new StringBuilder();
        while(t-- > 0){
            st = new StringTokenizer(br.readLine());
            boolean[] visited = new boolean[10000];
            String[] command = new String[10000];

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            Queue<Integer> q = new LinkedList<>();
            visited[a] = true;
            Arrays.fill(command, "");
            q.offer(a);

            while(!q.isEmpty()){
                int c = q.poll();

                // D 명령어 : 2를 곱하고 10000으로 나눈 나머지를 구한다.
                int D = c * 2 % 10000;
                if(!visited[D]) {
                    visited[D] = true;
                    command[D] = command[c] + "D";
                    if(b == D) break;
                    q.offer(D);
                }

                // S 명령어 : -1을 더하고 0이면 9999를 입력한다.
                int S = c == 0 ? 9999 : c-1;
                if(!visited[S]) {
                    visited[S] = true;
                    command[S] = command[c] + "S";
                    if(b == S) break;
                    q.offer(S);
                }

                // L 명령어 : 좌측으로 한 칸씩 이동
                int L = (c % 1000) * 10 + (c / 1000);
                if(!visited[L]) {
                    visited[L] = true;
                    command[L] = command[c] + "L";
                    if(b == L) break;
                    q.offer(L);
                }

                // R 명령어 : 우측으로 한 칸씩 이동
                int R = (c % 10) * 1000 + c / 10;
                if(!visited[R]){
                    visited[R] = true;
                    command[R] = command[c] + "R";
                    if(b == R) break;
                    q.offer(R);
                }
            }
            sb.append(command[b]).append("\n");
        }

        System.out.println(sb);
        br.close();
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.