백준 9019번: DSLR(Python/Java)

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

9019번: DSLR

 

 

 

접근

---

구현만 차근히 잘 해낸다면 어렵지 않게 풀 수 있는 너비 우선 탐색 문제. 때문에 굳이 풀이 방법을 포스팅할 필요가 있나 싶지만, 구현 방식에서 재밌는 아이디어가 있어 기록해놓기 위해 풀이를 작성한다.

 

문제에서 주어진 네 가지 명령 중, D와 S는 굉장히 쉽게 구현할 수 있다. D는 그냥 현재 값을 두배 한 다음에 10000으로 나눈 나머지를 가져가면 된다. '결과 값이 9999 보다 큰 경우에는 10000으로 나눈 나머지를 취한다.'라고 문제 조건에 나와있는데 이걸 보고 9999를 기준으로 조건문을 넣어야 하나? 생각하지 말자. 한 번만 더 생각해보면 9999보다 크든 작든 10000으로 나누면 D명령으로 구해야 하는 값을 바로 구할 수 있다. S 명령 또한 그냥 구현하면 된다.

 

내가 헷갈렸던 부분은 L과 R 명령이었다. 숫자 순서를 바꾸는 것을 어떻게 해야 하는지 아이디어가 안 떠올랐기 때문이었다. 근데 한 번만 더 생각해보니 이 역시 D 명령만큼 간단했다. 아주 조금의 아이디어만 생각해내면 복잡한 구현이 필요 없다. L 연산의 경우 네 자리 숫자에서 맨 첫 숫자를 맨 뒤로 보내는 것이다. 그렇다면 전체 수를 1000으로 나눠보자. 몫은 당연히 네 자리 숫자의 첫 번째 자릿수가 나올 것이다. 그렇다면 나머지는? 첫 번째 자릿수를 제외한 세 숫자가 나온다. 이제 모든 문제는 해결됐다. 네 자리 숫자를 1000으로 나눈 나머지에 10을 곱하고 몫을 더해주면 맨 첫 숫자를 맨 뒤로 보낼 수 있다. R 명령 또한 이를 조금 응용해서 구하면 된다. 이제 너비 우선 탐색을 통해 답만 구하면 된다.

 

 

 

풀이

---

Python

from collections import deque

roundNum = int(input())

orderList = ["D", "S", "L", "R"]
allResult = ""
for i in range(roundNum):
    startNum, goalNum = map(int, (input()).split())
    visitList = [False for i in range(10000)]
    visitList[startNum] = True
    
    bfsDeque = deque()
    bfsDeque.append([startNum, ""])
    resultCheck = False
    result = ""
    while bfsDeque:
        thisDeque = bfsDeque.popleft()

        for i in range(4):
            subNum = 0

            if orderList[i] == "D":
                subNum = (thisDeque[0]*2)%10000
            elif orderList[i] == "S":
                if thisDeque[0] != 0:
                    subNum = thisDeque[0]-1
                else:
                    subNum = 9999
            elif orderList[i] == "L":
                subNum = (((thisDeque[0]%1000)*10) + thisDeque[0]//1000)
            elif orderList[i] == "R":
                subNum = (((thisDeque[0]%10)*1000) + thisDeque[0]//10)
            
            if not visitList[subNum]:
                if subNum != goalNum:
                    visitList[subNum] = True
                    bfsDeque.append([subNum, thisDeque[1]+orderList[i]])
                else:
                    visitList[subNum] = True
                    resultCheck = True
                    result = thisDeque[1] + orderList[i]
                    break
        
        if resultCheck:
            break

    allResult += result + "\n"

print(allResult)

 

Java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);

        String[] orderList = {"D", "S", "L", "R"};
        int roundNum = Integer.parseInt(scan.nextLine());

        String allResult = "";
        for(int i = 0 ; i < roundNum ; i++){
            String[] firstLine = (scan.nextLine()).split(" ");
            int startNum = Integer.parseInt(firstLine[0]), goalNum = Integer.parseInt(firstLine[1]);
            boolean[] visitList = new boolean[10000];
            visitList[startNum] = true;
            
            Queue<String[]> bfsQueue = new LinkedList<>();
            bfsQueue.add(new String[] {Integer.toString(startNum), ""});
            String result = "";
            loop:
            while(!bfsQueue.isEmpty()){
                String[] thisQueue = bfsQueue.poll();
                int thisNum = Integer.parseInt(thisQueue[0]);

                for(int j = 0 ; j < 4 ; j++){
                    int subNum = 0;

                    if(orderList[j].equals("D")){
                        subNum = (thisNum*2)%10000;
                    }else if(orderList[j].equals("S")){
                        if(thisNum != 0){
                            subNum = thisNum-1;
                        }else{
                            subNum = 9999;
                        }
                    }else if(orderList[j].equals("L")){
                        subNum = (((thisNum%1000)*10) + thisNum/1000);
                    }else if(orderList[j].equals("R")){
                        subNum = (((thisNum%10)*1000) + thisNum/10);
                    }

                    if(!visitList[subNum]){
                        if(subNum != goalNum){
                            visitList[subNum] = true;
                            bfsQueue.add(new String[] {Integer.toString(subNum), (thisQueue[1] + orderList[j])});
                        }else{
                            visitList[subNum] = true;
                            result = (thisQueue[1] + orderList[j]);
                            break loop;
                        }
                    }
                }
            }

            allResult += result + "\n";
        }

        System.out.println(allResult);

    }

}

 

 

 

후기

---

전혀 어렵지 않은 문제인데 왜 레벨이 골드 4까지 올라갔을까 생각해봤다. 아무래도 위에서 얘기한 간단한 아이디어 때문이 아닐까 생각한다. L과 R 명령에서 다른 방법을 통해 저 숫자를 지지고 볶아서 구현하면 무조건 시간 초과, 메모리 초과가 뜨기 때문이다. 간단한 산수 아이디어지만 바로 떠올리지 못해 조금 자존심이 상하기도 했다. 무조건 코드로 만들어보려고만 하지 말고 이런 작은 아이디어들을 적극적으로 떠올리고 활용해보도록 해야겠다.