13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
비슷한 문제
0. 수빈이의 이동 방법 3가지를 활용해, 동생에게 가장 빠르게 갈 수 있는 경우 찾기
- 3개의 선택지가 있는 탐색 문제.
- 어떤 선택지를 먼저 선택하느냐에 따라 해가 나오지 않거나 큰 해가 나오는 경우가 존재하므로 DFS가 아닌 BFS 사용
- 단, 걷는 방법과 순간이동 방법의 소모 시간이 다르므로, BFS의 형식만 따를 뿐 이론적으로 BFS로 작동하지 않는다
- ex) +1+1+1+1과 *2 *2 *2 *2는 각각 4번의 이동을 하지만, 소모 시간은 4초 / 0초로 다름
- 전체 경우의 수를 탐색한다
1. 수빈이의 시작지점 N에서 BFS방식으로 +1, -1, *2 지점을 큐에 넣으며 진행한다
2. 수빈이가 어떤 칸 X에 W초를 걸려 도달했는데, 이미 해당 칸에 W보다 적은 시간으로 도달한 기록이 있다면, 더이상 탐색하는것은 의미가 없다.
- 어떤 칸 X에 몇초만에 도달하였는지를 num 배열에 저장하여, 현재의 시간이 더 작을때에만 진행하도록 한다
- 숨바꼭질 기본 문제와는 달리, 순간이동의 소모 시간이 0이므로, num[X]가 0인지 아닌지만으로는 판단할 수 없다
3. 수빈이의 현재 위치가 동생의 위치보다 크다면, +1 *2 연산을 진행할 필요는 없다
- 마찬가지로, 수빈이의 현재 위치가 동생의 위치보다 작다면, -1 연산을 진행할 필요는 없다
4. 정리하자면,
- 현재 좌표 X가 동생의 좌표 K보다 작으며, X+1 좌표의 이전 접근 시간이 현재 시간보다 클때만 진행+갱신
- 현재 좌표 X가 동생의 좌표 K보다 작으며, X*2 좌표의 이전 접근 시간이 현재 시간보다 클때만 진행+갱신
- 현재 좌표 X가 동생의 좌표 K보다 크며, X-1 좌표의 이전 접근 시간이 현재 시간보다 클때만 진행+갱신하며,
- K좌표에 도달하는 순간 연산 횟수를 출력, 종료한다
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int len=100001;
int[] num = new int[len*2];
int[] way = new int[len*2];
Arrays.fill(num, Integer.MAX_VALUE);
way[N]=1;
num[N]=0;
Queue<Integer> q = new LinkedList<Integer>();
q.offer(N);
while(!q.isEmpty()) {
int temp = q.poll();
if(temp < K && num[temp*2]>num[temp]) {
way[temp*2]+=way[temp];
if(num[temp*2]!=num[temp]+1)q.offer(temp*2);
num[temp*2]=num[temp];
}
if(temp < K && num[temp+1]>num[temp]) {
way[temp+1]+=way[temp];
if(num[temp+1]!=num[temp]+1)q.offer(temp+1);
num[temp+1]=num[temp]+1;
}
if(temp-1 >= 0 && num[temp-1]>num[temp]) {
way[temp-1]+=way[temp];
if(num[temp-1]!=num[temp]+1)q.offer(temp-1);
num[temp-1]=num[temp]+1;
}
}
System.out.println(num[K]);
}
}
'알고리즘 문제 풀이 > BOJ 골드' 카테고리의 다른 글
| [백준] 1922 - 네트워크 연결 (0) | 2021.06.11 |
|---|---|
| [백준] 1647 - 도시 분할 계획 (0) | 2021.06.07 |
| [백준] 1007 - 벡터 매칭 (0) | 2021.06.07 |
| [백준] 12851 - 숨바꼭질 2 (0) | 2021.05.29 |
| [백준] 10942 - 팰린드롬? (0) | 2021.05.19 |
| [백준] 16724 - 피리 부는 사나이 (0) | 2021.05.16 |
| [백준] 1068 - 트리 (0) | 2021.05.14 |
