[백준(Baekjoon)][자바(java)] 1697 : 숨바꼭질 / DFS와 BFS

 

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 {

	static class Dot {
		int pos, time; // pos : position
		public Dot(int pos, int time) {
			this.pos = pos;
			this.time = time;
		}
	}

	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; Dot dot;
		int answer = 0, i, pos, time, pos_next[], p, time_next;

		Deque<Dot> queue = new ArrayDeque<>();
		queue.add(new Dot(n, 0));

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

		// BFS
		loop:
		while (!queue.isEmpty()) {
			dot = queue.remove();
			pos = dot.pos;
			time = dot.time;
			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 Dot(p, time_next));
				v[p] = true;
			}
		}

		System.out.println(answer);
	}
}