○ 문제 요약
수빈이가 동생의 위치로 간다고 할 때, 가장 적은 시간이 걸리는 방법의 시간을 출력해라.
○ 문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st ;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
if(N >= K){
System.out.println(N - K);
}else{
System.out.println(bfs(N,K));
}
}
public static int bfs(int N, int K){
Queue<Integer> q = new LinkedList<>();
int[] arr = new int[100001];
q.offer(N);
arr[N] = 1;
while(!q.isEmpty()){
int now = q.poll();
for(int i = 0 ; i < 3; i++){
int next;
if(i==0){
next = now - 1;
}else if(i == 1){
next = now + 1;
}else{
next = now * 2;
}
if(next == K){
return arr[now];
}
if(0 <= next && next < 100001){
if(arr[next] == 0){
q.offer(next);
arr[next] = arr[now] + 1;
}
}
}
}
return 0;
}
}
알고리즘 분류가 너비 우선 탐색이라고 명시되어 있었지만 그럼에도 코드를 작성하는 것이 쉽진 않았다.
Queue를 생성해주고 값을 저장할 배열도 하나 생성해주었다. 이 배열은 인덱스로 연산하고 나온 값을 가지고 값은 몇 초가 지났는지 알 수 있도록 초를 넣어줄 것이다. 아무래도 글로 설명하는 것보다 그림으로 보는 것이 빠른 이해를 도와주므로 그림으로 보자.
now가 5일 때, arr 배열에 위 그림과 같이 값이 들어가고 Queue에는 4, 6, 10이 들어간다.
문제에서는 힌트로 5 -> 10 -> 9 -> 18 -> 17 경로를 주었지만 5 -> 4 -> 8 -> 16 -> 17도 가능하다는 것을 알았다.
next와 k가 같아졌으므로 아래 조건식이 성립한다.
어떤 경로로 17이라는 값이 되었든지 arr[16]이나 arr[18] 모두 4라는 값을 갖는 것은 같으므로 arr[16]나 arr[18]이 출력되면 4초 뒤에 수빈이와 동생이 같은 위치에 있다는 것을 알 수 있다.
○ 결과
'문제풀이 > 백준' 카테고리의 다른 글
백준 12018. Yonsei TOTO(JAVA) (0) | 2022.06.10 |
---|---|
백준 5397. 키로거(JAVA) (0) | 2022.05.24 |
백준 1620. 나는야 포켓몬 마스터 이다솜 (0) | 2022.05.18 |
백준 10816. 숫자 카드2 (JAVA) (0) | 2022.05.17 |
백준 1920. 수 찾기(JAVA) (0) | 2022.05.16 |