[백준] 13549 숨바꼭질3

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

2020-11-16

---

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

public class Main13549 {
	public static int N, K, answer;
	public static int dx[] = { 2, -1, 1};
	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 != 0) {
					nx = x + dx[i];
					ny += (y + 1);
				} else {
					nx = x * dx[0];
					ny = y;
				}

				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);
	}
}

void2017.tistory.com/115

[백준] 1697 숨바꼭질

위의 숨바꼭질과 문제가 똑같다. 다만 조건 중에 2*X의 위치로 이동하는 경우 0초로 계산된다.

 

이 부분 때문에 틀렸었는데, 단순하게 -1 -> +1 -> 2로 계산하는 순서를 바꿔서, 2 -> -1 -> +1로 계산하니 통과가 됐다. 2의 가중치?가 가장 적어서 그렇다.

 

애초에 바로 수빈이와 동생이 만났을 때 while문을 끝내는 것이 아니라, 각각 이동한 방법대로 따로 값을 출력받아 최솟값을 찾았으면, 안 틀렸을 것이다.

 

 

---

알고리즘 분류에 '다익스트라'와 '0-1 BFS' 가 있었다. 나중에 두 알고리즘을 공부하고 다시 풀어봐야겠다.