백준 - 1697번 숨바꼭질 (실버 1)

1. 큐에 처음위치를 저장하고, 방문기록 해두기

2. 큐에서 하나씩 빼며 +1,-1,*2 연산하기

경계조건: 0~100,000까지

방문기록: 방문한 곳은 또 방문하지 않도록 하기 

-> 이 조건을 안 해두면 무한루프로 실패

3. K와 같다면 방문기록을 출력 후 종료

아니라면 큐에 넣고 방문기록=전꺼 +1 하기

 

* 처음부터 N과 K가 같을 수도 있음

-> 이 경우 큐에 넣을 필요가 없음. 바로 종료

import java.io.*;
import java.util.*;

class Main{

    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(
                new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(
                new OutputStreamWriter(System.out));

        String[] input=br.readLine().split(" ");
        int N=Integer.parseInt(input[0]);
        int K=Integer.parseInt(input[1]);

        Queue <Integer> q=new LinkedList<>();
        int[] dx={-1,1,2};
        q.add(N);
        int[] visited=new int[200001]; //방문 여부 확인
        //10000인 경우 2배를 하게 되면 20000이 되므로 200001로 설정

        if(N==K){ //처음부터 같은 경우를 추가안해서 계속 틀림.
            bw.write("0\n");
            bw.flush();
            bw.close();
            return;
        }
        //K가 되면 종료
        while (!q.isEmpty()){
            int x=q.poll();
            for(int i=0;i<dx.length;i++) {
                int nx;
                if (i == 2) {
                    nx = x * dx[i];
                } else {
                    nx = x + dx[i];
                }
                if (nx < 0 || nx > 100000 ) { //경계 조건
                    /*N은 0~100,000까지
                    K도 0~100,000까지*/
                    continue;
                }
                if (nx == K) {
                    bw.write((visited[x]+1) + "\n");
                    bw.flush();
                    bw.close();
                    return;
                }
                if(visited[nx]!=0) continue; //방문했던 곳은 패스
                
                q.add(nx);
                visited[nx]=visited[x]+1;;
            }
        }
    }
}