문제 내용은 입력으로 두 수를 받아 왼쪽 수에 +1과 *2를 사용해서 오른쪽 수를 만들 경우, 최소 연산 횟수는 몇번인지를 출력하는 것인데 만들지 못하는 경우는 주어지지 않는다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
// 정수 a를 k로 만들기 https://www.acmicpc.net/problem/25418
public class AtoK {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] split = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{split[0], 0});
int ans = 0;
boolean[] visited = new boolean[split[1] + 1];
while (!queue.isEmpty()) {
int[] poll = queue.poll();
visited[poll[0]] = true;
if (poll[0] == split[1]) {
ans = poll[1];
break;
}
if (poll[0] * 2 < visited.length) {
if (!visited[poll[0] * 2]) {
queue.add(new int[]{poll[0] * 2, poll[1] + 1});
}
}
if (poll[0] + 1 < visited.length) {
if (!visited[poll[0] + 1]) {
queue.add(new int[]{poll[0] + 1, poll[1] + 1});
}
}
}
System.out.println(ans);
}
}
문제 내용을 보면 단순 계산으로 접근할 경우 1111 가지고 997651 구하느라 무한한 시간을 허비해야 하는데, visited 배열과 BFS를 사용해주면 문제를 무한한 시간 허비 없이 해결할 수 있는데
boolean 타입의 visited 배열을 목표값보다 + 1이 더 큰 크기로 생성한 후, Queue에 시작 값과 0을 배열 형태로 넣어준 후 Queue를 돌려주면서 현재 값을 visited 처리해주고, * 2와 +1을 해주면서 횟수를 증가시키면서 진행하되, 이미 방문한 값에는 또 방문하지 않게 해주고
Queue에서 값을 뽑을 때마다, 뽑은 값이 목표 값과 같다면 바로 Queue를 중단해주면서, 시도 횟수를 출력해주면 끝이다
Leave a Reply