[Baekjoon] 25418_정수 a를 k로 만들기

Silver III

문제(출처: https://www.acmicpc.net/problem/25418)

---

< 정수 a를 k로 만들기 >

 

문제 풀이 

 

bfs를 활용해서 문제를 해결했다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _25418_ { // 정수 a를 k로 만들기

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int a = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		boolean visited[] = new boolean[1000001];

		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { a, 0 });

		int result = 0;

		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			if (temp[0] * 2 <= 1000000 && !visited[temp[0] * 2]) {
				if (temp[0] * 2 == k) {
					result = temp[1] + 1;
					break;
				}
				visited[temp[0]*2]=true;
				queue.add(new int[] { temp[0] * 2, temp[1] + 1 });
			}

			if (temp[0] + 1 <= 1000000 && !visited[temp[0] + 1]) {
				if (temp[0] + 1 == k) {
					result = temp[1] + 1;
					break;
				}
				visited[temp[0]+1]=true;
				queue.add(new int[] { temp[0] + 1, temp[1] + 1 });
			}
		}
		System.out.println(result);
	}
}

 

Main

변수)
a : 입력값
k : 입력값
visited : 방문 여부
queue : [정수, 연산 횟수]
result : 최소 연산 횟수

 

- 입력 값 정수(a, k) 입력

- queue에 시작값으로 a와 연산 횟수 0을 배열로 넣음

- queue가 빌 때까지 반복

1) queue에서 꺼낸 값에서 2를 곱한 값이 범위 안이며 아직 방문하지 않았다면 방문 표시 및 queue에 추가

2) queue에서 꺼낸 값에서 1을 더한 값이 범위 안이며 아직 방문하지 않았다면 방문 표시 및 queue에 추가

: 각 경우에서 k 값과 일치하다면 종료

- result 출력

---

---