[BJ1697] 숨바꼭질

 백준 - 숨바꼭질 

문제 링크

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

1697번: 숨바꼭질

 

문제 입출력

5 17

4

 

문제 풀이

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;


// N: 수빈이 위치 
// K: 동생 위치 
// ans: 몇 초만에 찾았는지 
public class Main {
	static int N, K, ans;
	static final int MAX = 100000;
	static boolean[] visit = new boolean[MAX + 1];

	static Queue<Integer> q = new ArrayDeque<>();


	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		bfs(N);

		System.out.println(ans);

	} // end main


	private static void bfs(int x) {
		visit[x] = true;
		q.offer(x);

		while (!q.isEmpty()) {
			int size = q.size();

			for (int i = 0; i < size; i++) {
				//System.out.println(size + " " + i + " " + q + " " + ans);
				int cx = q.poll();

				if (cx == K) return;

				int x1 = cx - 1;
				int x2 = cx + 1;
				int x3 = cx * 2;

				if (x1 >= 0 && !visit[x1]) {
					visit[x1] = true;
					q.offer(x1);
				}

				if (x2 <= MAX && !visit[x2]) {
					visit[x2] = true;
					q.offer(x2);
				}

				if (x3 <= MAX && !visit[x3]) {
					visit[x3] = true;
					q.offer(x3);
				}

			}

			ans++;
		}

	} // end bfs
}

• 출력된 형태는 size, i, queue, ans
• bfs 를 이용하여 풉니다.
• bfs 는 너비를 탐색하면서 가기 때문에 최소를 구하기에 좋습니다.
• bfs 큐가 비지 않을 때까지 돌면서 또 한번, 큐에 쌓인 사이즈만큼 돌아줍니다.
• 그렇게 되면 depth 만큼 돌게 됩니다. 그렇게 depth 가 쌓이게 되어 정답을 찾으면 그 depth 를 리턴하면 최소값이 됩니다.

 

 

 

 

 

 

 

 

# 백준 숨바꼭질 java # 백준 숨바꼭질 java bfs

---