[BOJ] 숨바꼭질 3

[13549] 숨바꼭질 3

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

• 수빈이의 위치 N
• 동생의 위치 K
• 동생을 찾는 가장 빠른 시간을 구하는 문제
• 수빈이가 할 수 있는 행동(위치 : X)
• 1. 걷기 : X + 1  또는 X - 1로 이동 (1초)
• 2. 순간이동 : 2 * X로 이동(0초)

 

 

Solution

• 덱을 사용한 BFS 풀이 방법
• 걷기와 순간이동의 가중치(시간)가 다르기 때문에 덱을 사용해 순간 이동은 덱의 앞에, 걷기는 덱의 뒤에 넣는 방법도 생각해 볼 수 있다.

 

 

소스코드

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	int[] count;

	public void go() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		count = new int[100001];
		Arrays.fill(count, -1);
		bfs(n);
		System.out.println(count[m]);
	}

	public void bfs(int n) {
		Deque<Integer> q = new LinkedList<>();
		q.offer(n);
		count[n] = 0;
		while (!q.isEmpty()) {
			int cur = q.poll();
			if (cur * 2 <= 100000 && count[cur * 2] < 0) {
				q.addFirst(cur * 2);
				count[cur * 2] = count[cur];
			}
			if (cur - 1 >= 0 && count[cur - 1] < 0) {
				q.addLast(cur - 1);
				count[cur - 1] = count[cur] + 1;
			}
			if (cur + 1 <= 20 && count[cur + 1] < 0) {
				q.addLast(cur + 1);
				count[cur + 1] = count[cur] + 1;
			}
		}
	}
    
	public static void main(String[] args) {
		Main main = new Main();
		main.go();
	}
}