0. 수빈이의 이동 방법 3가지를 활용해, 동생에게 가장 빠르게 갈 수 있는 경우 찾기
- 3개의 선택지가 있는 탐색 문제.
- 어떤 선택지를 먼저 선택하느냐에 따라 해가 나오지 않거나 큰 해가 나오는 경우가 존재하므로 DFS가 아닌 BFS 사용
1. 수빈이의 시작지점 N에서 BFS방식으로 +1, -1, *2 지점을 큐에 넣으며 진행한다
2. 수빈이가 어떤 칸 X에 W초를 거쳐 도달했는데, 이미 해당 칸에 W보다 적은 시간으로 도달한 기록이 있다면, 더이상 탐색하는것은 의미가 없다.
- BFS는 W초에서 갈수있는 모든 지점을 완료한 후 W+1초의 지점들에 대해 작업하므로, 값의 유/무로만 판단해도 무방하다
- X번 노드에 도달했을 때의 이동 횟수를 num배열에 저장하여, 그 값이 없는 좌표에 대해서만 진행한다
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.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];
num[N]=1;
Queue<Integer> q = new LinkedList<Integer>();
q.offer(N);
while(num[K]==0) {
int temp = q.poll();
if(temp < K && num[temp+1]==0) {
num[temp+1]=num[temp]+1;
q.offer(temp+1);
}
if(temp-1 >= 0 && num[temp-1]==0) {
num[temp-1]=num[temp]+1;
q.offer(temp-1);
}
if(temp < K && num[temp*2]==0) {
num[temp*2]=num[temp]+1;
q.offer(temp*2);
}
}
System.out.println(num[K]-1);
}
}
'알고리즘 문제 풀이 > BOJ 실버' 카테고리의 다른 글
[백준] 17276 - 배열 돌리기 (0) | 2021.10.10 |
---|---|
[백준] 1325 - 효율적인 해킹 (0) | 2021.09.25 |
[백준] 5567 - 결혼식 (0) | 2021.08.08 |
[백준] 14241 - 슬라임 합치기 (0) | 2021.07.07 |
[백준] 5639 - 이진 검색 트리 (0) | 2021.04.14 |
[백준] 2564 - 경비원 (0) | 2021.04.13 |
[백준] 2110 - 공유기 설치 (0) | 2021.04.13 |