[백준(Baekjoon)][자바(java)] 1697 : 숨바꼭질 / 그래프와 순회

 

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

1697번: 숨바꼭질

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()),
			k = Integer.parseInt(st.nextToken());
		br.close();

		final int max = 100001;
		int answer = 0, i, pos, time, pos_next[], p, time_next, dot[];

		Deque<int[]> queue = new ArrayDeque<>(); // position, time
		queue.add(new int[]{n, 0});

		boolean v[] = new boolean[max];
		v[n] = true;

		loop : 
		while (!queue.isEmpty()) {
			dot = queue.remove();
			pos = dot[0];
			time = dot[1];
			pos_next = new int[]{pos * 2, pos + 1, pos - 1};
			time_next = time + 1;
			for (i = 0; i < 3; i++) {
				p = pos_next[i];
				if (p < 0 || p >= max || v[p])
					continue;
				if (p == k) {
					answer = time_next;
					break loop;
				}
				queue.add(new int[]{p, time_next});
				v[p] = true;
			}
		}

		System.out.println(answer);
	}
}