[백준 1697] 숨바꼭질

출처 : https://www.acmicpc.net/problem/1697

BFS 문제입니다.

큐를 생성해 N을 넣고

현재 점 N을 기준으로

N-1

N+1

N*2

를 모두 구한뒤

이것이 범위를 벗어나지 않으면서 처음 탐색된 값일경우

배열의 현재위치값 + 1 해주고 큐에 넣어줍니다.

이것을 M이 될때까지 반복.

 

	public class Q1697 {
	static int[] move = new int[3]; // seq: -1, +1, *2
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int[] arr = new int[100002];
	int start = Integer.parseInt(st.nextToken());
	int end = Integer.parseInt(st.nextToken());
	Queue<Integer> queue = new LinkedList<Integer>();
	arr[start] = 1;
	queue.add(start);
	boolean brk = false; //이중반복문 탈출
	while(!queue.isEmpty()) {
	int current = queue.poll();
	int next = 0;
	move[0] = current - 1;
	move[1] = current + 1;
	move[2] = current * 2;
	for(int i=0; i<3; i++) {
	next = move[i];
	if(move[i]<0 || move[i]>100000) {
	continue;
	}
	if(arr[next]>0) {
	continue;
	}else {
	arr[next] = arr[current]+1;
	if(next == end) {
	brk = true;
	break;
	}
	queue.add(next);
	}
	}
	if(brk) {
	break;
	}
	}
	System.out.print(arr[end]-1);
	}
	}

view raw Q1697.java hosted with ❤ by GitHub