[백준] 1697 숨바꼭질

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

2020-11-16

---

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main1697 {
	public static int N, K, answer;
	public static int dx[] = { -1, 1, 2 };
	public static Queue<int[]> q;
	public static boolean vtd[];

	public static void solve() {
		loop: while (!q.isEmpty()) {
			int tmp[] = q.poll();
			int x = tmp[0];
			int y = tmp[1];
			for (int i = 0; i < dx.length; i++) {
				int nx = 0;
				int ny = 0;
				if (i != 2)	nx = x + dx[i];
				else nx = x * dx[2];

				ny += (y + 1);

				if (nx < 0 || nx > 100000 || ny > answer)
					continue;
				if (nx == K) {
					answer = ny;
					break loop;

				} else if (!vtd[nx] && ny < answer) {
					q.add(new int[] { nx, ny });
				}
				vtd[nx] = true;
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		K = sc.nextInt();
		vtd = new boolean[100001];
		q = new LinkedList<>();

		q.add(new int[] { N, 0 });
		vtd[N] = true;
		answer = 987654321;
		if (N == K)
			answer = 0;
		else
			solve();
		System.out.println(answer);
	}
}

숨바꼭질3을 풀다가 예전에 못 풀었던 숨바꼭질부터 다시 풀게 되었다.

 

1. 수빈이의 현재 위치를 queue에 넣는다.

 

2. queue에서 값을 하나씩 제거하며, -1, +1, *2 일때 각각 값을 계산한다. 이 때, 값이 0, 100000 범위 밖을 벗어나면 안된다.

 

3. 동생이 있는 자리에 도달하면 끝낸다. 만약 아닐 경우, 방문한적이 없는 자리일 때 다시 queue에 넣고 반복한다.