[백준] 9019번 DSLR JAVA (자바) 풀이

문제 9019(BFS)

 

 :  네 개의 명령어 D, S, L, R

    계산기에는 레지스터 = 0 이상 10,000 미만의 십진수 저장 가능

 

    예) 레지스터에 저장된 n (n의 네 자릿수를 d1, d2, d3, d4)

          즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)

1. D = n x 2 (결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지)
2. S = n - 1 (n이 0 이라면 9999 가 대신 레지스터에 저장)
3. L = n의 각 자릿수를 왼편으로 회전 (d2, d3, d4, d1)
4. R = n의 각 자릿수를 오른편으로 회전 (d4, d1, d2, d3)

 :  A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램

 

 

[입력]

 :  첫 줄에 T 개의 테스트 케이스

 :  각 테스트 케이스에 두 개의 정수 A와 B(A ≠ B & 공백으로 분리)

     (A는 초기 값 / B는 최종 값 / A 와 B는 모두 0 이상 10,000 미만)

  

 

 [출력]

 :  최소한의 명령어 나열을 출력 (가능한 명령어 나열이 여러가지면, 아무거나 출력)

 

 

 [문제접근]

 

 1. 4개의 연산 모두 돌려보기

1. D = n x 2 (결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지)
   •  int D = (next*2) % 10000;
   • 모든 수를 10000으로 나누어도 상관없다
     10000을 넘지 않는 경우는 나머지로 숫자가 그대로 나온다
2. S = n - 1 (n이 0 이라면 9999 가 대신 레지스터에 저장)
   • int S = next == 0 ? 9999:next-1;
   • 말 그대로 연산 작성하기
3. L = n의 각 자릿수를 왼편으로 회전 (d2, d3, d4, d1)
   • int L = (next%1000*10) + (next/1000);
   • 어렵지만 찾아내자 규칙을!!
     왼쪽으로 민다는 얘기는 맨 앞에 숫자를 뒤로 보낸다는 뜻
     그렇다면 1000으로 나눈 나머지에 *10 하면 맨 앞 숫자를 뺀 남은 수는 완성
     1234라면 2340이 된 것! 
     그리고 1000으로 나눈 몫을 바로 더하면 된다
4. R = n의 각 자릿수를 오른편으로 회전 (d4, d1, d2, d3)
   • int R = (next%10*1000) + (next/10);
   • 어렵지만 찾아내자 규칙을!!
     오른쪽으로 민다는 얘기는 맨 뒤 숫자를 앞으로 보낸다는 뜻
     그렇다면 10으로 나눈 나머지에 *1000 하면 맨 앞 숫자 완성
     1234라면 4000이 된 것! 
     그리고 10으로 나눈 몫을 바로 더하면 된다  

 

 2. 연산 시 주의할 것

• 0도 포함이다! 
  6은 0006으로 생각하고 연산해라
  즉 모든 수는 4자리의 숫자로 이루어져 있다는 사실!
  
• 맨 앞자리 수가 필요하다면 1000으로 나눈 몫!
• 맨 뒷자리 수가 필요하다면 10으로 나눈 몫!

       

 3. 출력 배열 사용하지 말고 큐에다 넣어버리기

• Object[]를 사용한다면 큐에 int형 String형 모두 넣을 수 있다

•  

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int A,B;
    static boolean visit[];
    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){
            visit = new boolean[10000];
            StringTokenizer st = new StringTokenizer(br.readLine());
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
            bfs(A,B);
        }
    }
    
    static void bfs(int a, int b){
        Queue<Object[]> q = new LinkedList<>();
        q.add(new Object[]{a,""});
        visit[a]=true;
        
        while(!q.isEmpty()){
            Object p[] = q.poll();
            int next = (int)p[0];
            String result = (String)p[1];
            
            if(next==b){
                System.out.println(result);
                return;
            }
            
            int D = (next*2) % 10000;
            if(!visit[D]){
                visit[D] = true;
                q.add(new Object[]{D,result+"D"});
            }
            
            int S = next == 0 ? 9999:next-1;
            if(!visit[S]){
                visit[S] = true;
                q.add(new Object[]{S,result+"S"});
            }
            
            int L = (next%1000*10) + (next/1000);
            if(!visit[L]){
                visit[L] = true;
                q.add(new Object[]{L,result+"L"});
            }
            
            int R = (next%10*1000) + (next/10);
            if(!visit[R]){
                visit[R] = true;
                q.add(new Object[]{R,result+"R"});
            }
        }
    }
}

 

 [해설]
     

 :  static int A,B;
    static boolean visit[];
   

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());  테스트케이스
        
 :  while(T-->0){
            visit = new boolean[10000];  매 케이스마다 방문기록 초기화
            StringTokenizer st = new StringTokenizer(br.readLine());
            A = Integer.parseInt(st.nextToken());  시작수
            B = Integer.parseInt(st.nextToken());  목표수
            bfs(A,B);  bfs실행
    }
    

 :  static void bfs(int a, int b){  시작 / 목표
        Queue<Object[]> q = new LinkedList<>();  object 사용해서 큐선언
        q.add(new Object[]{a,""});  큐에 서로 다른 자료형 변수 넣기
        visit[a]=true;  방문체크
        
        while(!q.isEmpty()){  큐가 빌 때까지 실행
            Object p[] = q.poll();  큐에서 뽑기
            int next = (int)p[0];  int로 캐스팅 
            String result = (String)p[1];  string으로 캐스팅
            
            if(next==b){  목표수가 완성되면 출력
                System.out.println(result);
                return;
            }
            
            int D = (next*2) % 10000;  D일 경우 2배하기
            if(!visit[D]){
                visit[D] = true;
                q.add(new Object[]{D,result+"D"});  큐에 새롭게 추가
            }
            
            int S = next == 0 ? 9999:next-1;  S일 경우 -1 하기
            if(!visit[S]){
                visit[S] = true;
                q.add(new Object[]{S,result+"S"});  큐에 새롭게 추가
            }
            
            int L = (next%1000*10) + (next/1000);  L일 경우 왼쪽으로 밀기
            if(!visit[L]){
                visit[L] = true;
                q.add(new Object[]{L,result+"L"}); 큐에 새롭게 추가
            }
            
            int R = (next%10*1000) + (next/10);  R일 경우 오른쪽으로 밀기
            if(!visit[R]){
                visit[R] = true;
                q.add(new Object[]{R,result+"R"});  큐에 새롭게 추가
            }
        }
    }
  


 

 

이제 풀어보러 갈께요 :)

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

 

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