[알고리즘] Java / 백준 / 숨바꼭질2 / 12851

[알고리즘] Java / 백준 / 숨바꼭질2 / 12851

문제

문제 링크

접근 방식

트리 구조처럼 수빈이의 현재 위치에서 -1, *2, +1로 가는 경우의 수를 확인한다

bfs를 활용하여 수빈이의 위치와 시간을 가지는 배열을 큐에 담은 후 동생의 위치에 도달할 때 까지 -1, *2, +1로 수빈이를 옮기고 시간도 추가하여 다시 큐에 담는다.

수빈이가 처음으로 동생에게 도달했을 때의 시간을 저장하고 해당 시간과 같은 시간으로 동생에게 도달할 때마다 카운트를 한다. 또한 해당 시간보다 더 많은 시간을 가지는 배열이 탐색되면 while문을 빠져나간다

코드

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_12851 {

	static int N,M;
	static int time;
	static int cnt;
	static boolean[] visited;
	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());
		M = Integer.parseInt(st.nextToken());
		
		time = 100001;
		cnt = 0;
		visited = new boolean[100001];
		bfs();
		
		System.out.println(time);
		System.out.println(cnt);
		
	}
	
	public static void bfs() {
		Queue<int[]> q = new LinkedList<>();
		
		q.add(new int[] {N,0});
		
		while(!q.isEmpty()) {
			
			int[] now = q.poll();
			visited[now[0]] = true;
			if(time < now[1]) break;
			if(now[0] == M) {
				if(time != now[1]) time = now[1];
				cnt++;
			}
			
			if(now[0]-1 >=0 && !visited[now[0]-1]) q.add(new int[] {now[0]-1,now[1]+1});
			if(now[0]*2 <= 100000 && !visited[now[0]*2]) q.add(new int[] {now[0]*2,now[1]+1});
			if(now[0]+1 <= 100000 && !visited[now[0]+1]) q.add(new int[] {now[0]+1,now[1]+1});
		
		}
		
	}

}