[백준] 25418번 A → K 최단 거리 구하기: BFS vs 역방향 그리디

 

 

 

 

문제

 

입력으로 양의 정수 A와 K가 주어지면, 아래 연산을 이용하여 A를 K로 변경하려고 한다. 정수 A를 변경할 때 사용할 수 있는 연산 종류는 다음과 같다.

• 연산 1: 정수 A에 1을 더한다.
• 연산 2: 정수 A에 2를 곱한다.

정수 A를 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력하자.

 

출처 : https://www.acmicpc.net/problem/25418

 

 

 

 

오늘도 알고리즘의 늪에서 허우적거리고 계신가요?

 

"아니, 그냥 1씩 계속 더하면 언젠가 도착하는 거 아냐?" 하시는 분들...

네, 도착은 하겠죠. 하지만 우리 인생은 유한합니다. 더 스마트하게 풀어봅시다!

 

[그림1] 무한도전 박명수

 

 

 

 

방법 1) BFS (너비 우선 탐색)

 

BFS는 마치 길치인 제가 구글 지도를 켜고 모든 골목길을 하나씩 다 가보는 것과 같습니다.

 

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int A = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        // 방문 체크와 거리를 한 번에! (초기값 -1)
        int[] dist = new int[K + 1];
        Arrays.fill(dist, -1);

        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(A);
        dist[A] = 0;

        while (!queue.isEmpty()) {
            int curr = queue.poll();

            if (curr == K) break;

            // 우리가 할 수 있는 행동: +1 또는 *2
            int[] nextSteps = {curr + 1, curr * 2};

            for (int next : nextSteps) {
                // 범위 안에 있고 아직 안 가본 곳이라면?
                if (next <= K && dist[next] == -1) {
                    dist[next] = dist[curr] + 1;
                    queue.offer(next);
                }
            }
        }
        System.out.println(dist[K]);
    }
}

• 특징 : 모든 경우의 수를 다 계산하기 때문에 정확합니다.
• 단점 : K값이 커질 수록 Queue에 쌓이는 데이터가 많아져 메모리가 증가합니다.

 

 

 

 

방법 2) 역방향 그리디

 

인생이 꼬였을 때는 처음부터 다시 생각하는 게 아니라,
"내가 도대체 어쩌다 이렇게 됐지?"라며 역순으로 추적하는 게 빠를 때가 있습니다.
이 문제도 마찬가지입니다!

 

K → A 로 갈 것이며

짝수면 무조건 나누고, 홀수면 1을 뺀다! 가 끝입니다!!

 

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int A = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int count = 0;

        while (K > A) {
            if (K % 2 == 1) {
                // 홀수면 선택지가 없어요. 무조건 1을 빼야 합니다.
                K--;
                count++;
            } else {
                // 짝수일 때, 2로 나눈 게 A보다 크거나 같으면 나누는 게 무조건 이득!
                if (K / 2 >= A) {
                    K /= 2;
                    count++;
                } else {
                    // 2로 나눴는데 A보다 작아진다면? 이제부터는 1씩 빼는 수밖에 없죠.
                    count += (K - A);
                    K = A; // 종료 조건
                }
            }
        }
        System.out.println(count);
    }
}

• 특징 : 계산 속도가 빛의 속도입니다. ^_^
• 단점 : 배열을 만들 필요도 없고, 메모리도 아낄 수 있습니다.

 

 

한눈에 정리 해보기

 

비교 항목	BFS (탐색형)	그리디 (역방향)
속도	보통 O(N)	매우 빠름 O(log N)
메모리	배열 필요 (많이 사용)	변수 몇 개면 끝!
생각의 난이도	직관적	머리를 좀 사용
추천 상황	모든 경우를 다 봐야할 때	최단 거리만 빠르게 구할 때

 

 

 

 

 

감사합니다.