[백준] 13549번 숨바꼭질 3 - Java, 자바
난이도
실버 5
문제
https://www.acmicpc.net/problem/13549
풀이
그래프 탐색, BFS로 해결
1697번 숨바꼭질에서 약간의 변형이 있는데 순간이동을 0초 후에 *2만큼 한다는 것이다.
순간이동할 때는 시간이 흐르지 않으므로 1초후에 발생하는 로직과 분리해서 처리한다.
-1, +1 하는 위치를 구하기 전에 2인 위치를 먼저 계산했다.
여기서 포인트는 2인 위치만을 계산한게 아니라 최대 위치인 100,000까지 전부 계산해둬야한다.
코드
package 그래프탐색;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class BOJ13549 {
static int n, k;
static int[] arr;
static Queue<Integer> q = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
if (n >= k) {
System.out.println(n - k);
} else {
System.out.println(bfs());
}
}
static int bfs() {
arr = new int[100001];
Arrays.fill(arr, -1);
q.add(n);
arr[n] = 0;
while (!q.isEmpty()) {
int x = q.poll();
if (x == k)
return arr[x];
int tmp = x * 2;
while (tmp <= 100000 && arr[tmp] == -1) {
arr[tmp] = arr[x];
q.add(tmp);
tmp *= 2;
}
for (int i = 0; i < 2; i++) {
int nx;
if (i == 0)
nx = x - 1;
else
nx = x + 1;
if (nx >= 0 && nx < 100001 && arr[nx] == -1) {
arr[nx] = arr[x] + 1;
q.add(nx);
}
}
}
return 0;
}
}
Author And Source
이 문제에 관하여([백준] 13549번 숨바꼭질 3 - Java, 자바), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmjieun/백준-13549번-숨바꼭질-3-Java-자바저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)