[백준] 1697 - 숨바꼭질

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

---

링크

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

1697번: 숨바꼭질

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

접근방법

  N이 움직일 수 있는 3가지 방법을 통해서 K 까지  갈 수 있는 가장 빠른 시간을 구하는 문제이다. 문제가 까다로운 이유는 순간이동과 백스텝(-1) 때문이다. 때문에 순간이동 후 뒤로 몇번 가는 경우나,  뒤로 간뒤 순간이동을 한 경우가 빠른 경우들이 나올 수 있다. 즉, 탐욕적으로 앞으로 가는 것만이 답은 아니다. N 갈 수 있는 모든 방향을 생각하되, 가장 빠른 경우를 찾아야한다. 이 점을 인지하고 풀이로 들어가자. 

풀이

 처음에 DP를 이용하여, 답을 구하려고 했다.  분할 정복으로 할 수 있을까에 대해 확신이 들지 않았다. DP[K] 값을 구하기 위해선 3가지 방법(앞,뒤,순간이동)을 생각하되, K가 홀 수이면, 또 순간이동 방법은 제외해야하고... N또한 0부터 시작이 아니기에 뒤로 가는 경우도 생각해야한다. 제어하기가 너무 까다로웠다. 예제인 5에서 17을 가는 방법을 한번 그려보고 생각을 바꾸었다. 

5 ~ 17 까지 가는 방법

 

 DFS 해답을 찾기엔 시간소모가 너무 크다. Depths 가 n일 때 최악의 경우 3^n의 깊이 탐색을 진행한다. 시간제한에도 치명적이므로, BFS를 이용했다. 이 문제에 BFS를 적용해야하는 또 다른 이유는 '중복'이 존재한다. 5에서 17을 가는 경우는  매우 여러 가지이다.

 

• 최소 루트 : 5 -> 10 -> 9 -> 18 -> 17
• 이외1 :  5 -> 6 -> 5 -> 10 -> 9 -> 18 -> 17
• 이외2:  5 - > 4 -> 5 -> 10 -> 9 -> 18 -> 17

BFS 탐색 중 탐색한 노드를 다시 한번 이동하는 경우를 제어할 수 있다. 본인의 경우 해당 노드로 가는 값이 더 빠른 경우에만, queue에 다시 추가하여 진행했고, 이외에 queue에서 제외하여 시간 소모를 줄였다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
         Main test =new Main();
    }


    public Main() throws IOException {
        BufferedReader br = new BufferedReader( new InputStreamReader(System.in ));
        StringTokenizer stk = new StringTokenizer(br.readLine()," ");

        int start = Integer.parseInt(stk.nextToken());
        int target = Integer.parseInt(stk.nextToken());

        System.out.println(solution(start,target));
    }

    private int solution(int start, int target) {
        //이동을 안할 때
        if(start == target){
            return 0;
        }
        
        int[] dp = new int[100001];
        Arrays.fill(dp,Integer.MAX_VALUE);
        
        Queue<IntPair> queue = new LinkedList<>();
        // Left : 현재 위치 , Right : 현재 위치까지 이동 횟수 
        queue.add(new IntPair(start,0));

        
        while (!queue.isEmpty()){

            IntPair cur = queue.poll();
            //다음 이동 횟수를 먼저 설정
            int move = cur.right+1;
            
            int next = 0;
            
            //현재 위치가 목적위치라면 out
            if(cur.left == target){
                break;
            }

            //이동할 수 있는 모든 방향을 구한다.
            for (int i = 0 ; i < 3 ; i++){
                if(i == 0){
                    next = cur.left-1;
                }else if(i == 1){
                    next = cur.left+1;
                }else{
                    next = cur.left*2;
                }
                
                //문제 범위 ( 배열초과 금지)
                if(next>=0 && next <100001){
                    //현재 이동 횟수보다 더 작은 값이 들어있다면
                    //그 노드로는 가는 의미가없다(이미 가는길이 있음)
                    if(dp[next] > move){
                        queue.add(new IntPair(next,move));
                        dp [next] = move;
                    }
                }

            }


        }

        return dp[target];
    }

    class IntPair{
        Integer left;
        Integer right;

        public IntPair(Integer left, Integer right) {
            this.left = left;
            this.right = right;
        }
    }
}

결과

 

 

 

 해당 문제를 풀 때, 가장 기본적인 디테일을 놓쳐서 두번을 틀렸다. 한번은 N=K 인 경우와 ArrayOutbound 에러 였다. 배열 값을 최대 값으로 잡았기 때문에, 처리해줘야할 가장 작은 경우와 BFS가 비약적으로 늘어날 때 제한 범위를 주지 않아 생긴 문제였다. 디테일에 조금 더 신경 쓰면 좋을 것 같다라고 느낀 문제다. 

 

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.