P148653. 마법의 엘리베이터

문제

제출 코드

• 사용 알고리즘 : 완전탐색

각 자리수마다 올림을 하거나 버림을 하는 경우를 모두 계산하여, 가장 최소 연산 횟수를 구하는 문제.

사실 주어진 제한범위가 크지 않아, 완전탐색을 돌려도 256가지밖에 나오지 않으니 DFS나 BFS로 풀 수 있는 문제이다.

그러나 나는 왜인지 모든 테케를 통과하지 못하고 오답에서 헤어나오지 못했고, 결국 다른사람의 풀이에서 힌트를 얻어 방법을 바꿔 풀었다.

디버깅이 매우매우매우 오래 걸린.. 힘겨웠던 문제. 나만 어렵게 푼거 같긴 하다.

import java.util.*;

class Solution {
    static class Number implements Comparable<Number>{
        int num, cnt;
        Number(int num, int cnt){
            this.num = num;
            this.cnt = cnt;
        }
        @Override
        public int compareTo(Number o){
            if(this.num == o.num) return this.cnt - o.cnt;
            else return this.num - o.num;
        }
    }

    public int solution(int storey) {
        int result = Integer.MAX_VALUE;
        int depth = ("" + storey).length();

        Queue<Number> queue = new LinkedList<Number>();
        queue.add(new Number(storey, 0));

        int d = 0;
        while(!queue.isEmpty()){
            int size=queue.size();

            for(int s=0; s<size; s++){
                Number now = queue.poll();
                int tmp = (int)(now.num / Math.pow(10, d)) % 10; // d번째 자리 숫자

                if(tmp <= 5){
                    int num = now.num - tmp * (int)Math.pow(10, d);
                    int cnt = now.cnt+tmp;

                    if(num>0) queue.add(new Number(num, cnt));
                    else result = Math.min(result, cnt);
                }
                if(tmp >= 5){
                    int num = now.num + (10-tmp) * (int)Math.pow(10, d);
                    int cnt = now.cnt+10-tmp;

                    queue.add(new Number(num, cnt));
                    if(num==0) result = Math.min(result, cnt);
                }
            }
            d++;
        }

        return result;
    }
}