백준 13549번 숨바꼭질3 [JAVA]

13549번: 숨바꼭질 3

 

풀이 방법

N의 위치에서 K위치까지 가는데 걸리는 최소의 시간을 구하는 문제였습니다.

 

저는 BFS알고리즘을 사용하여 문제를 풀었으며,

for문을 이용해 순간 이동할 때와 걸을 경우를 구분하여 우선순위 큐에 넣어주었습니다. 방문을 확인하는 visited배열을 이용하여 해당 이동한 곳이 방문한 곳이 아닐 경우에만 이동할 수 있도록 구현했습니다. 우선순위 큐로 움직인 횟수가 가장 작은 것부터 움직일 수 있도록 했기 때문에 만약 현재 위치가 동생이 있는 곳이라면 시간을 출력해주고 반복문을 종료해주었습니다. 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_BJ_13549_숨바꼭질3 {
    
    static class info implements Comparable<info>{
        int position, time;
 
        public info(int position, int time) {
            super();
            this.position = position;
            this.time = time;
        }
 
        @Override
        public int compareTo(info o) {
            return this.time-o.time;
        }
    }
    
    static int N,K;
    static boolean [] visited;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
 
        visited = new boolean[100001];
        
        move();
    }
    
    public static void move() {
        Queue<info> pq = new LinkedList<>();
        
        pq.add(new info(N,0));
        
        while(!pq.isEmpty()) {
            info temp = pq.poll();
            
            if(temp.position == K) {
                System.out.println(temp.time);
                return;
            }
            
            int nx = 0;
            for(int i=0;i<3;i++) {
                if(i==0) nx = temp.position*2;
                else if(i==1) nx = temp.position-1;
                else if(i==2) nx = temp.position+1;
                
                if(range(nx) && !visited[nx]) {
                    if(i==1 || i==2) pq.add(new info(nx, temp.time+1));
                    else pq.add(new info(nx, temp.time));
                    visited[nx] = true;
                }
            }
        }
    }
    
    public static boolean range(int x) {
        return x>=0 && x<visited.length;
    }
 
}