[자바] 백준 1697번 숨바꼭질. 2021-06-28

처음에는 2차원 평면상의 이동이 아니라서 DP로 풀어야 하나.. 하고 끙끙댔는데, 알고보니 +1,-1, *2 의 이동가능 범위(계층이동)의 1차원 수직선상의 이동으로 BFS를 이용하면 쉽게 풀리는 문제였다. 큐에 한계층 이동했을때를 현재 좌표에 반영해서 넣기 곤란했는데, 새로 움직인 좌표를 저장하는 nexti[ ]라는 배열을 만들어서 쉽게 해결하였다. 

앞으로  좌표를 수직선이나 평면에 표현할 수 있고,  이동함+최솟값 조건의 문제는 DP가 아닌 BFS부터 생각해서 풀어야겠다.

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

public class Main {


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

        int N=s.nextInt();
        int K=s.nextInt();
        int[] arr=new int[100001];
        int[] cntarr=new int[100001];
        boolean[] value=new boolean[100001];
        arr[N]=1;
        cntarr[N]=0;

        Queue<Integer> queue= new LinkedList<>();
        int[] nexti=new int[3];
        queue.add(N);
        while (!queue.isEmpty()){
            int nowi= queue.poll();
            if(nowi==K){
                System.out.println(cntarr[nowi]);
                break;
            }
            nexti[0]=nowi+1;
            nexti[1]=nowi-1;
            nexti[2]=nowi*2;
            for (int i = 0; i < nexti.length; i++) {
                if(nexti[i]>=100001||nexti[i]<0){
                    continue;
                }
                if(value[nexti[i]]){
                    continue;
                }
                queue.add(nexti[i]);
                cntarr[nexti[i]]=cntarr[nowi]+1;
                value[nexti[i]]=true;
            }
        }



        }
    }

 

 

dfu

역시 주말에 휴식을 취하고 다시 공부하니 공부효율이 오른 느낌이다. 집중이 바로 잘된다. 역시 쉬는것도 공부라는  말이 맞는 말인거 같다. 공부의 순도를 높이는것도 중요하지만, 그에 맞게 적절한 주기에 뇌를 쉬어주는 것도 매우 중요하다는 것을 깨달았다. 주5회 공부 2일 휴식 이 루틴을 절때 깨지말자. 공부와 운동을 시작하고, 자존감이랑 내 프로그래밍실력도 함께 느는거 같아 행복하고, 내가 자랑스럽다.