문제

BOJ 13549: 숨바꼭질 3 https://www.acmicpc.net/problem/13549

풀이

조건

• 목적지까지 가는데 방법이 3가지가 있다.
  • 현재 위치 X 2 : 이동하는 데 걸리는 시간은 0이다.
  • 현재 위치 + 1 : 이동하는 데 걸리는 시간은 1이다.
  • 현재 위치 - 1 : 이동하는 데 걸리는 시간은 1이다.

풀이 순서

• BFS를 사용하여 해결한다.
• 현재 위치 X 2로 이동하는 경우엔 걸리는 시간이 0이기 때문에 다른 이동 방법보다 우선순위를 높게 둔다.
• BFS 내부에서 PriorityQueue를 사용하여 걸리는 시간이 더 적은 경우가 더 앞으로 오도록 한다.
• PriorityQueue 내부에서 값들이 우선순위에 따라 위치가 이동하므로 방문 처리는 PriorityQueue에서 뽑아낼 때 해준다.

코드

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

public class Main {
    
	static int N, K;
	static int[] map = new int[200011]; // 찾으러 다니는 배열
	static boolean[] isVisited = new boolean[200011]; // 방문 처리 할 배열
	
	static int[] dx = {1, -1};
    
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    	
    	N = Integer.parseInt(st.nextToken()); // 수빈이 위치
    	K = Integer.parseInt(st.nextToken()); // 동생 위치
    	
    	bfs(N);

    }
    
    static void bfs(int start) {
    	// 우선 순위 큐를 사용하여
    	// 큐 내부에서 이동하는 시간이 낮은 경우가 더 앞으로 오도록 해준다.
    	PriorityQueue<Pos> que = new PriorityQueue<>();
    	
    	que.add(new Pos(start, 0));
    	
    	while(!que.isEmpty()) {
    		Pos p = que.poll();
    		
    		int nowX = p.x;
    		int nowCnt = p.cnt;
    		 // 큐 내부에서 값의 위치가 바뀌므로 뽑아 낼 때 방문 처리를 해준다.
    		isVisited[nowX] = true;
    		// 종료 조건
    		if(nowX == K) {
    			System.out.println(nowCnt);
    			return;
    		}
    		
    		// *2 거리로 점프 하는 경우부터 탐색한다.
    		int jump = nowX * 2;
    		if(jump < 100001 && !isVisited[jump]) {
    			que.add(new Pos(jump, nowCnt));
    		}
    		
    		// +1, -1 경우를 탐색한다.
    		for(int t=0; t<2; t++) {
    			int nx = nowX + dx[t];
    			
    			if(nx >= 0 && nx < 100001 && !isVisited[nx]) {
    				que.add(new Pos(nx, nowCnt + 1));
    			}
    		}
    	}
    	
    }
    
    static class Pos implements Comparable<Pos>{
    	int x, cnt;
    	
    	Pos(int x, int cnt){
    		this.x = x;
    		this.cnt = cnt;
    	}
    	
        // 오름차순으로 넣음 (시간이 더 적게 걸리는 것이 더 앞으로 오게)
    	@Override
    	public int compareTo(Pos o) {
    		return this.cnt - o.cnt;
    	}
    }
}

정리

• PriorityQueue를 사용하여 더 쉽게 해결할 수 있었다.