[백준] 알고리즘 분류(그리디 알고리즘,JAVA)16953번, A → B

문제 링크

16953번: A → B

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 두 숫자 A와 B가 주어지며 A를 B로 만드는 최소 연산 횟수 + 1를 결과로 출력합니다.

2. 연산은 2를 곱하거나 가장 오른쪽에 1을 추가하는 연산 2가지가 존재합니다.

3. 연산을 이용해도 B를 만들지 못하면 -1을 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. BFS탐색을 통해서 A에 대해 연산을 진행하여 가장 먼저 B에 도착하는 횟수를 구합니다.

 

3. 최소 연산 값을 결과로 출력합니다.

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

A : 2

B : 162

 

2. BFS탐색을 통해서 A에 대해 연산을 진행하여 가장 먼저 B에 도착하는 횟수를 구합니다.

 

연산 횟수 : 1

 

연산1 : 2 × 2 = 4

연산2 : 21 

 

연산 횟수 : 2

 

연산1 : 4 × 2 = 8

연산1 : 21 × 2 = 42

연산2 : 41 

연산2 : 212(목표값보다 크기 때문에 더 이상 탐색하지 않아도된다. X)

 

연산 횟수 : 3

 

연산1 : 8 × 2 = 16

연산1 : 41 × 2 = 82

연산1 : 42 × 2 = 84

연산2 : 81

연산2 : 411(목표값보다 크기 때문에 더 이상 탐색하지 않아도된다. X)

연산2 : 421(목표값보다 크기 때문에 더 이상 탐색하지 않아도된다. X)

 

연산 횟수 : 4

 

연산1 : 16 × 2 = 32

연산1 : 82 × 2 = 164(목표값 도착!)

연산1 : 84 × 2 = 168

연산2 : 161(목표값보다 크기 때문에 더 이상 탐색하지 않아도된다. X)

연산2 : 821(목표값보다 크기 때문에 더 이상 탐색하지 않아도된다. X)

연산2 : 841(목표값보다 크기 때문에 더 이상 탐색하지 않아도된다. X)

연산2 : 811(목표값보다 크기 때문에 더 이상 탐색하지 않아도된다. X)

 

3. 최소 연산 값 + 1을 결과로 출력합니다.

 

4 + 1 = 5 을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 이용하여 숫자 A와 B를 나누었습니다.
• search함수를 사용하여 최소 연산 횟수 + 1를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 BFS탐색을 진행하여 최소 연산 횟수값을 구합니다.
• search함수에서 탐색을 통해 B에 도달하지 못하면 -1을 반환합니다.
• search함수는 boolean[] 배열을 이용하여 각 숫자에 대해 방문을 확인합니다.

 

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


public class Main {
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력되는 두 숫자 저장
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        bw.write(search(start, end) + "");	//BFS 탐색 결과 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS탐색을 진행하는 함수
    static int search(int start, int end){
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[end+1];	//방문 확인 함수
        q.add(start);
        visited[start] = true;
        int answer = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0;i<size;i++){
                int cur = q.poll();
                if(cur == end)		// B 숫자에 도착
                    return answer+1;	//최소 연산 횟수 + 1 반환
                long temp = cur * 2L;	//연산 1. ×2 진행
                if(temp <= end && !visited[(int) temp]){
                    visited[(int)temp] = true;
                    q.add((int) temp);
                }
                temp = cur * 10L + 1;	//연산 2. 오른쪽에 1 추가하기
                if(temp <= end && !visited[(int) temp]){
                    visited[(int)temp] = true;
                    q.add((int) temp);
                }
            }
            answer++;

        }
        return -1;
    }
}