[BAEKJOON]16953 A → B

문제 요약

• 알고리즘 분류: dfs
• 난이도: Silver2
• 문제내용:
  • 아래와 같이 2가지 연산이 가능하다.
    • ×2
    • 1을 오른쪽추가한다.
  • A, 에서 B까지 최소 몇번 연산가능한지 구해라.
• 사이트: https://www.acmicpc.net/problem/16953

16953번: A → B

문제풀이

 이번 문제는 dfs 응용하는 문제이다. dfs 대한설명은 여기에서 확인 해보면 된다.

문제 접근 방법

 

  bfs를 응용하는 것인데 위 그림 처럼 queue에 현재 값을 연산후 B보다 작거나 같을때  queue에 저장하면 하고 현재 값 연산 횟수에 +1을 더하면 끝이다. 

from collections import deque

A, B = map(int, input().split())
numbers = [-1] * (B + 1)
numbers[A] = 1
queue = deque([A])

while queue:
    num = queue.popleft()
    
    for fnum in (num * 2, num * 10 + 1):
        if fnum <= B and numbers[fnum] == -1:
            numbers[fnum] = numbers[num] + 1
            queue.append(fnum)
    
print(numbers[B])

 위에 방문 횟수를 저장하기 위해 배열이나/인덱스를 저장하면 메모리초과가 나와서 queue에 (연산 후 값, 연산 횟수 + 1) 이런 식으로 저장해야 한다.

 위 그림 처럼 큐에 저장해서 B값이 같을때 연산 횟수를 출력하면 된다.

정리

1. 큐를 선언하고 (A, 1)에 저장한다.
2. 큐에 값을 꺼내고 * 2, * 10 + 1연산후 B보다 작을때 q에 (연산 결과 값, 연산 횟수)를 저장한다.
3. 연산 횟수를 저장시 큐에 꺼낸 값에 연산 횟수 + 1을 한다.
4. 큐에 꺼낸 값이 B일때 연산 회수를 저장한다. 만약 큐를 다꺼내고 B값이 없을 경우 -1로 출력한다.

Code

Python

from collections import deque
import sys

A, B = map(int, input().split())
queue = deque([(A, 1)])

while queue:
    num, move = queue.popleft()
    if num == B:
        print(move)
        sys.exit()

    for fnum in (num * 2, num * 10 + 1):
        if num <= B:
            queue.append((fnum, move + 1))        

print(-1)

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 NUMBER16953 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		
		Queue<long[]> queue = new LinkedList<long[]>();
		long[] data = {A, 1};
		queue.add(data);
		long num, move;
		long result = -1;
		
		while(! queue.isEmpty()) {
			data = queue.poll();
			num = data[0];
			move = data[1];
			// B까지 연산 했을경우
			if(num == B) {
				result =  move;
				break;
			}
			
			if(num * 2 <= B) {
				data = new long[2];
				data[0] = num * 2;
				data[1] = move + 1;
				queue.add(data);
			}
			
			if(num * 10 + 1 <= B) {
				data = new long[2];
				data[0] = num * 10 + 1;
				data[1] = move + 1;
				queue.add(data);
			}
		
		}
		
		System.out.println(result);
	}
}