[백준 16953 / A → B / JAVA / BFS, DFS]

https://www.acmicpc.net/problem/16953

16953번: A → B

 

문제 접근

답을 보면 쉬우나 매번 떠올리는 게 쉽지 않다.

 

DFS

재귀로 계속 돌면서 A, B가 같아지는 순간 최소 횟수를 저장하고 모든 재귀를 다 돌고 main 메서드로 돌아갔을 때, 최소 횟수에 변경이 있었으면 count를 출력하고 변경이 없었다면 A, B가 같아지는 순간이 없었기에 -1출력

 

import java.util.*;
import java.io.*;

public class Main {
	static long A;
	static long B;
	static int count = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
	   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   StringTokenizer st = new StringTokenizer(br.readLine());
	   
	   A = Long.parseLong(st.nextToken());
	   B = Long.parseLong(st.nextToken());
	   
	   dfs(A, 1);
	   if(count == Integer.MAX_VALUE) System.out.println(-1);
	   else System.out.println(count);
	}
	
	private static void dfs(long a, int cnt) {
		
		if(a == B) {
			count = Math.min(count, cnt);
			return;
		}
		if(a > B) return;
		
		dfs(a * 2, cnt+1); // 2를 쭉 곱해감
		dfs(a * 10 + 1, cnt+1); // 2를 쭉 곱하다가 돌아오면 1을 추가
	}
}

 

BFS

큐에 A값을 넣어놓고 큐 크기만큼 반복문 실행, 2를 곱하거나 1을 추가하는 연산 실행하고 큐에 다시 저장 → 해당 연산으로 횟수 + 1

반복문 돌아서 위의 연산 다시 실행하면서 A == B 되는 순간 count 출력 후 종료

A > B가 되서 더 이상 큐에 값이 들어가지 않으면 -1 출력 후 종료

import java.util.*;
import java.io.*;

public class Main {
	static long A;
	static long B;
	static int count = 1;
	
	public static void main(String[] args) throws IOException {
	   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   StringTokenizer st = new StringTokenizer(br.readLine());
	   
	   A = Long.parseLong(st.nextToken());
	   B = Long.parseLong(st.nextToken());
	   
	   bfs();
	}
	
	private static void bfs() {
		
		Queue<Long> q = new LinkedList<>();
		q.add(A);
		
		while(!q.isEmpty()) {
			
			int qs = q.size();
			
			while(qs > 0) {
				qs--;
				long value = q.poll();
				
				if(value == B) {
					System.out.println(count);
					return;
				}
				if(value * 2 <= B) q.add(value * 2); // A, B가 같더라도 일단 값 넣어놓고 다음 연산 때 == B에서 return시킴
				if(value * 10 + 1 <= B) q.add(value * 10 + 1);
			}
			// 곱하거나 1을 추가하는 1회의 행위
			count++;
		}
		// A가 B보다 커져서 더 이상 q에 값이 들어가지 않게되면
		System.out.println(-1);
		
	}
}