[백준BOJ]13549번 숨바꼭질3.java

 

백준 저지에서 숨바꼭질3를 자바를 통해 풀어 보았다. 

 

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

13549번 숨바꼭질3.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

13549번 숨바꼭질3

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

설명

bfs를 통해 풀 수 있는 문제이다. 다익스트라의 개념이 살짝 필요하다. 

 

방문 가능한 위치는 0~100000이다. 따라서 100001 크기의 배열을 만들었다. 

 

배열에는 현재까지 해당 위치로 도달할 수 있는 가장 짧은 시간이 저장된다. 배열에 접근하려면 최초 접근하거나 해당 배열에 저장된 시간보다 적을 때만 가능하다. 이 과정을 bfs로 접근한다. 

 

bfs를 돌다가 K 배열에 도착하면 해당 값을 return 한다.

코드

//13549번 숨바꼭질3.java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 숨바꼭질3_13549 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int[] visit = new int[100001];
		Arrays.fill(visit, -1);
		
		System.out.println(bfs(visit, N, K));
	}
    
    static int bfs(int[] visit,int N, int K) {
    	Queue<Integer> q = new LinkedList<Integer>();
    	visit[N]=0;
    	q.add(N);
    	while(!q.isEmpty()) {
    		int now = q.poll();
    		
    		if(now==K) {
    			return visit[now];
    		}
    		
    		if(2*now<=100000 && (visit[2*now]==-1 || visit[2*now] > visit[now])) {
    			visit[2*now] = visit[now];
    			q.add(2*now);
    		}
    		if(now+1<=100000 && (visit[now+1]==-1 || visit[now+1] > visit[now]+1)) {
    			visit[now+1] = visit[now]+1;
    			q.add(now+1);
    		}
    		if(now-1>=0 && (visit[now-1]==-1 || visit[now-1] > visit[now]+1)) {
    			visit[now-1] = visit[now]+1;
    			q.add(now-1);
    		}
    		
    	}
    	return 0;
    }
    
}