[백준] 1326번 - 폴짝폴짝 java

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

난이도 : S2

Tag : BFS/DFS

풀이 일자 : 2025-03-03

문제 탐색하기

N : 징검다리의 개수

N개의 수: 각 징검다리에 쓰여있는 값 (배수의 위치로만 점프)

a : 출발하는 a번째 징검다리

b : 도착하는 b번째 징검다리

 

각 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 이동하여,

a번 징검다리에서 출발하여 최소한의 점프 횟수로 b번 징검다리까지 가는 게 핵심입니다.

N은 최대 10,000개고 a,b는 N보다 작거나 같습니다.

또한, 징검다리에 쓰여있는 정수는 10,000보다 작거나 같은 자연수입니다.

이때, a에서 b로 갈 수 없다면 -1을 출력합니다.

가능한 시간복잡도

개구리가 현재위치에서 징검다리마다 점프할 수 있는 모든 경우의 수를 확인해야 합니다.

a번 징검다리에서 b번 징검다리로 이동할 때 개구리는 앞뒤로 각 배수만큼 점프할 수 있고,

경우의 수는 아래처럼 다양합니다.

• 앞으로만 점프할 경우
• 뒤로 점프했다 앞으로 점프할 경우
• 목적지를 지나쳤다가 다시 뒤로 점프할 경우
• .....

이때 O(N)이 1억 개 안의 연산 크기를 만족시켜야 합니다.

 

1. O(N^2)이라면? 

•  각위치에서 모든 가능한 점프 경로를 따지는 경우입니다.
• N이 10,000이므로 1억의 시간복잡도를 가지므로 시간 초과가 날 수 있습니다.

2. O(N)이라면?

•  각 위치를 한 번만 방문하여 점프하는 경우입니다. 
• N이 10,000이므로 안정적으로 시간 복잡도 내에서 실행 가능합니다.

 

알고리즘 선택

탐색 알고리즘 중 BFS를 사용해 보겠습니다.

BFS는 최단 거리 탐색에 주로 사용되며, 한번 방문한 노드는 다시 방문할 필요 없습니다.

개구리가 같은 징검다리를 다시 밟지 않으므로 최대 O(N)으로 해결 가능합니다. 

---

코드 설계하기

1. 문제의 input을 받습니다.
2. BFS를 구현하고, 최소 점프 횟수를 구합니다.

시도 회차 수정 사항

1회차

• 간단한 BFS로 생각하고 문제를 풀었다. 하지만 조건에 뒤로 이동해서는 안된다는 경우가 없으므로 개구리가 뒤로 점프하는 경우를 고려하지 않았다. 개구리는 앞으로만 점프한다고 가정했으므로 틀렸다.
• 그래서 BFS에 각 배수만큼 1번째 위치까지 뒤로 이동하는 경우도 추가했다.

2회차

• 맨 처음 위치로 이동할 수 있다면 맨 마지막 위치로도 점프할 수 있어야 했다. 도착지를 지나치고 점프 후 다시 뒤로 점프하여 도착할 수 있으니 말이다.
• 앞으로 이동할 때 범위를 처음에는 next < b+1로 했지만 맨 끝까지 이동할 수 있기에 next < n으로 수정했다.

 

---

정답코드

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int[] steppingStones = new int[n];
        for(int i=0; i<n; i++){
            steppingStones[i] = sc.nextInt();
        }
        int a = sc.nextInt()-1;
        int b = sc.nextInt()-1;
        
        boolean[] visited = new boolean[n];
        boolean isArrived = false;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{a,0});
        visited[a] = true;
        
        while(!q.isEmpty()){
            int[] curr = q.poll();
            int currNum = curr[0]; // 현재 위치
            int jumps = curr[1]; //현재까지의 점프 횟수
            
            if(currNum == b){
                isArrived = true;
                System.out.println(jumps);
                break;
            }
            
            int step = steppingStones[currNum];
            
            for(int next=currNum+step; next<n; next+=step){
                if(!visited[next]){
                    visited[next] = true;
                    q.add(new int[] {next,jumps+1});
                }
            }
            
            for(int next=currNum-step; next>-1; next-=step){
                if(!visited[next]){
                    visited[next] = true;
                    q.add(new int[] {next,jumps+1});
                }
            }
        }
        
        if(!isArrived) System.out.println(-1);
    }
}