백준 1697번: 숨바꼭질

 

 

너비 우선 탐색(BFS, Breadth-First Search) 알고리즘을 사용하여 주어진 숫자 a에서 b로 가는 최소 횟수를 구하는 문제입니다.

주어진 정수 a와 b에 대해, a에서 시작해 여러 가지 연산을 통해 b에 도달하려면 최소 몇 번의 연산이 필요한지를 구하세요. 가능한 연산은 다음과 같습니다:

1. 현재 숫자에서 1을 뺀다.
2. 현재 숫자에 1을 더한다.
3. 현재 숫자에 2를 곱한다.

코드

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

public class Main {
    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());

        System.out.println(bfs(a, b));
    }


    static int bfs(int a, int b) {
        if (a == b) return 0;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(a);

        int[] visited = new int[100001];

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

            for (int next : new int[] {now - 1, now + 1, now * 2}) {
                if (next >= 0 && next <= 100000 && visited[next] == 0) {
                    queue.offer(next);
                    visited[next] = visited[now] + 1;
                    if (next == b) return visited[next];
                }

            }
            
        }

        return -1;
    }
    
}

 

BFS 함수 (bfs(int a, int b)):

• BFS 탐색을 통해 a에서 b로 가는 최소 연산 횟수를 구합니다.
• visited 배열을 사용하여 각 숫자를 몇 번째 연산에서 방문했는지 기록합니다. 초기값은 모두 0으로 설정되며, 각 숫자는 처음 방문할 때 그때의 연산 횟수를 기록합니다.
• BFS를 수행하면서 각 숫자에서 가능한 세 가지 연산을 진행합니다:
  • 현재 숫자에서 1을 뺀다.
  • 현재 숫자에 1을 더한다.
  • 현재 숫자에 2를 곱한다.
• 연산을 통해 도달한 숫자는 queue에 넣고, 해당 숫자가 b와 같으면 연산 횟수를 반환합니다.
• 만약 BFS 탐색이 끝날 때까지 b에 도달하지 못하면 -1을 반환합니다.

큐와 방문 처리

• 큐(Queue<Integer> queue)를 사용하여 BFS 탐색을 진행합니다. 큐에 숫자를 넣고, 큐에서 숫자를 꺼내어 그 숫자에서 가능한 연산을 진행합니다.
• visited[next] 값은 각 숫자를 처음 방문했을 때 연산 횟수를 기록합니다. 이를 통해 이미 방문한 숫자는 다시 방문하지 않도록 하여 중복 탐색을 방지합니다.

시간 복잡도

• 각 숫자에서 3개의 연산을 수행하고, 각 연산에 대해 next 값이 유효한지 확인합니다. 각 연산은 O(1) 시간에 처리할 수 있습니다.
• 큐에 최대 100,001개의 숫자가 들어갈 수 있으며, 각 숫자에 대해 3개의 연산을 수행하므로 총 연산 횟수는 대체로 O(3 * 100001)입니다.
• 상수인 3을 제외하고, 시간 복잡도는 **O(N)**입니다. 여기서 N은 100,001이므로, O(N) 시간 복잡도가 됩니다.