BOJ 1697 숨바꼭질

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

 

문제 분석

- bfs를 사용하여 동생을 만날 때까지 탐색한다.

cf) 수빈이와 동생이 있는 점의 위치는 0~100000 사이다. 

 

 

문제 풀이

1) 수빈이와 동생의 위치를 받는다.

2) bfs를 통해 수빈이가 동생을 만날 때까지 탐색한다.

3) 만나면 해당 값이 최소인지 비교하고 마지막에 bfs를 나와서 정답을 출력한다.

 

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 {
	private static int N, K, min;
	private static boolean[] visited;

	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st;
		min = Integer.MAX_VALUE;

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		visited = new boolean[100001];

		bfs(N);
		System.out.println(min);

	}// input()

	private static void bfs(int sx) {
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(sx, 0));
		visited[sx] = true;

		while (!q.isEmpty()) {
			Node cur = q.poll();
			int r = cur.x;
			int d = cur.depth;
			
			if (r == K) {
				min = Math.min(min, (d));
			}
			
			for (int i = 0; i < 3; i++) {
				int nr;
				if (i == 0) {
					nr = r + 1;
				} else if (i == 1) {
					nr = r - 1;
				} else {
					nr = r * 2;
				}
								
				if (nr >= 0 && nr < visited.length) {
					if (!visited[nr]) {
						q.add(new Node(nr, d + 1));
						visited[nr] = true;
					}
				}
			}
		}
	}// bfs

	public static void main(String[] args) throws IOException {
		input();
	}// main

	static class Node {
		int x, depth;

		public Node(int x, int depth) {
			this.x = x;
			this.depth = depth;
		}
	}// Node-class
}// class-end