Lv.2 마법의 엘리베이터 [JAVA]

문제링크

성공 여부(걸린 시간): 성공(13분 42초)

아이디어

처음에 DP로 할까? 했으나 수가 꽤 크고 일반 dp배열로 만드는 것 보다
다익스트라나 BFS를 활용하면 더 간단하게 풀 수 있을거란 생각이 들어 풀게 되었다.
비슷한 문제가 백준에 존재했어서 쉽게 떠올릴 수 있었다. (뮤탈리스크 2 ?? 참고)

난 다익스트라로 진행해주었다.

• 방문처리는 HashSet
  왜냐면 방문배열 인덱스를 1억까지 하기엔 낭비가 너무 심하다.
• 그리고 이동할 층 수는 10의 0승부터 8승까지 반복문으로 더하고 빼준 것 각각 큐에 삽입
• 가장 중요한 우선순위큐는 목표 층 수와의 절대값 차가 작은 순으로 정렬

이 세가지만 해주면 끝.

풀이 코드

import java.util.*;

class Solution {
    public int solution(int storey) {
        int answer = 0;
        PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(o1->Math.abs(o1[0]-storey)));
        HashSet<Integer> visited = new HashSet<>();
        q.add(new int[]{0, 0});
        visited.add(0);

        while(!q.isEmpty()){
            int [] cur = q.poll();
            int curFloor = cur[0];
            int curCnt = cur[1];
            if(curFloor==storey){
                return curCnt;
            }
            for(int i=0; i<=8; i++){
                //+- 한번씩 가능하다면 q에 넣어주기
                int moveFloorUp = curFloor+(int)Math.pow(10, i);
                int moveFloorDown = curFloor-(int)Math.pow(10, i);
                if(!visited.contains(moveFloorUp)){
                    q.add(new int []{moveFloorUp, curCnt+1});
                    visited.add(moveFloorUp);
                }
                if(moveFloorDown >= 0 && !visited.contains(moveFloorDown)){
                    q.add(new int []{moveFloorDown, curCnt+1});
                    visited.add(moveFloorDown);
                }
            }

        }
        return answer;
    }
}