백준 25418번 정수 A를 K로 만들기-JAVA

📝문제

📝알고리즘

//양의 정수 A와 K를 입력받고
//bfs(A,K)의 반환값을 출력
//bfs 메서드는 다음과 같이 작성
//start를 큐에 넣고 방문했다고 표시
//최소 연산 횟수 min을 0으로 초기화
//큐가 빌 때까지 다음을 반복
//한 층의 요소들인 현재 큐에 있는 모든 요소들을 탐색
//큐에서 가장 앞에 있는 요소를 꺼내서
//그 값이 end와 같으면 min을 반환
//그렇지 않고 값이 범위를 초과하지 않고 아직 방문하지 않은 경우
//value+1이 1000000 이하이고 방문하지 않았으면 큐에 넣고 방문 처리
//value*2가 1000000 이하이고 방문하지 않았으면 큐에 넣고 방문 처리
//한 층 탐색이 끝나면 min을 증가시킴

❌틀린 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int A = scanner.nextInt();
        int K = scanner.nextInt();
        
        System.out.print(bfs(A, K));
    }

    public static int bfs(int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[1000001]; 
        queue.add(start);
        visited[start] = true;
        
        int min = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int value = queue.poll();
                if (value == end) return min;

                if (!visited[value + 1]) {
                    queue.add(value + 1);
                    visited[value + 1] = true;
                }
                if (!visited[value * 2]) {
                    queue.add(value * 2);
                    visited[value * 2] = true;
                }
            }
            min++;
        }
        return -1;
    }
}

📝틀린 이유

런타임 에러 발생

➡️value+1 또는 value*2가 1000000을 초과하면 visited 배열 접근 시 배열 범위를 초과하면서 에러가 발생(ArrayIndexOutOfBoundsException)

📝수정한 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int A = scanner.nextInt();
        int K = scanner.nextInt();
        
        System.out.print(bfs(A, K));
    }

    public static int bfs(int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[1000001]; 
        queue.add(start);
        visited[start] = true;
        
        int min = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int value = queue.poll();
                if (value == end) return min;

                if (value + 1 <= 1000000 && !visited[value + 1]) {
                    queue.add(value + 1);
                    visited[value + 1] = true;
                }
                if (value * 2 <= 1000000 && !visited[value * 2]) {
                    queue.add(value * 2);
                    visited[value * 2] = true;
                }
            }
            min++;
        }
        return -1;
    }
}

✅배열 범위를 초과하지 않도록 조건을 추가해서 해결함