[BOJ] 12851. 숨바꼭질2

BFS를 사용하는 문제이다.

다른 숨바꼭질 시리즈와 다르게 몇가지 경로로 목적지에 도달할 수 있냐를 체크해야 함으로 visit 체크를 queue에 offer할 때가 아니라 queue에 poll 할때 체크해주었다. 또한, 처음 도달한 경우가 최솟값이므로 그 값을 이용하는 과정을 거쳤다.

package chap05;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_12851_숨바꼭질2 {
    
    
    static int start,dest;
    static boolean[] visit;
    static Queue<Pos> queue;
    
    static int count,result;
    
    static class Pos{
        int loc,sec;
        public Pos(int l,int s) {
            loc=l;sec=s;
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in)); 
        StringTokenizer st =new StringTokenizer(br.readLine());
        
        start= Integer.parseInt(st.nextToken());
        dest= Integer.parseInt(st.nextToken());
        
        queue=new LinkedList<>();
        count=0; result=Integer.MAX_VALUE;
        visit=new boolean[100001];
        bfs();
        System.out.println(result);
        System.out.println(count);
    }
    
    static void bfs() {
        queue.offer(new Pos(start, 0));
        
        while(!queue.isEmpty()) {
            Pos cur= queue.poll();
            visit[cur.loc]=true;
            
            //그 이후의 갱신
            if(cur.loc==dest && result!=Integer.MAX_VALUE) {    
                if(cur.sec==result) {
//                    System.out.println(cur.loc + " , " +cur.sec);
                    count++;
                }
            }
            
            //첫번째 갱신
            if(cur.loc==dest && result==Integer.MAX_VALUE) {
                result=cur.sec;
                count++;
//                System.out.println(cur.loc + " , " +cur.sec);
            }
            
            for(int dir=0;dir<3;dir++) {
                int nextLoc=0;
                if(dir==0) {
                    nextLoc=cur.loc-1;
                }else if(dir==1) {
                    nextLoc=cur.loc+1;
                }else if(dir==2) {
                    nextLoc=cur.loc*2;
                }
                if(nextLoc<0 || nextLoc>100000)
                    continue;
                
                if(visit[nextLoc]==false)
                    queue.offer(new Pos(nextLoc, cur.sec+1));
            }
        }
    }
}