[알고리즘 TIL] Q1697(BFS)

문제

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

트러블 슈팅

1. visited 타입 선택

처음에는 방문 여부를 판단하기 위해 ArrayList를 사용했고, .contains()로 중복 방문을 방지했다. 하지만 contains()는 내부적으로 선형 탐색을 수행하기 때문에 시간 복잡도는 O(N) 이다. 입력 범위가 0부터 100,000까지인 이 문제에서 결국 시간 초과가 발생했다.

boolean[] visited = new boolean[100001];

처럼 배열을 활용하면 O(1)로 즉시 방문 여부를 확인할 수 있어, 훨씬 효율적인 BFS 구현이 가능하다.

 

2. 좌표 범위 조건 누락

문제에서는 0 ≤ K ≤ 100000이라는 명확한 좌표 범위 제한이 있었지만,
처음에는 이를 코드에 명시하지 않아 예외가 발생했다.

• DFS로 풀던 초기에는 스택 오버플로우
• BFS로 바꾼 이후에도 ArrayIndexOutOfBoundsException 발생

범위를 벗어나는 좌표(예: -1, 100001 등)가 큐에 들어가면서 에러가 났다.
→ 문제에서 제공하는 제한 조건은 반드시 코드로 명시적으로 검증해야 한다는 교훈을 얻었다.

 

3. 이동 좌표 배열로 리팩토링

처음에는 nextPos + 1, nextPos - 1, nextPos * 2를 각각 조건문으로 처리하며 중복된 로직을 반복적으로 작성했다.

하지만 이후 다음과 같이 이동 가능한 위치를 배열에 담고, 반복문을 활용하니 코드가 훨씬 간결해지고 가독성도 좋아졌다.

int[] nextPos = new int[] {pos +1, pos-1, pos*2};
            for(int i=0;i<nextPos.length;i++){
                if(nextPos[i] >= 0 && nextPos[i] <= 100000 && !visited[nextPos[i]]) {
                    queue.add(new Integer[]{nextPos[i],count+1});
                    visited[nextPos[i]]=true;
                }
            }

구현

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

public class Q1697 {

    static boolean[] visited = new boolean[100001];
    static int result;
    static LinkedList<Integer[]> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] inputStrArr = br.readLine().split(" ");
        int N = Integer.parseInt(inputStrArr[0]);
        int K = Integer.parseInt(inputStrArr[1]);

        queue.add(new Integer[]{N,0});

        while(!queue.isEmpty()){
            Integer[] popData = queue.pop();
            Integer pos = popData[0];
            Integer count = popData[1];

            if(pos==K) {
                result = count;
                break;
            }

            int[] nextPos = new int[] {pos +1, pos-1, pos*2};
            for(int i=0;i<nextPos.length;i++){
                if(nextPos[i] >= 0 && nextPos[i] <= 100000 && !visited[nextPos[i]]) {
                    queue.add(new Integer[]{nextPos[i],count+1});
                    visited[nextPos[i]]=true;
                }
            }
        }

        bw.write(result+"");
        bw.flush();
        bw.close();
        br.close();
    }
}