[BOJ] 1326번: 폴짝폴짝

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

1326번: 폴짝폴짝

 

 

1. 문제 설명 

개구리는 일렬로 놓여 있는 징검다리를 건넌다. 각 징검다리에는 숫자가 쓰여 있고 쓰여진 수의 배수만큼 떨어져 있는 곳으로만 이동할 수 있다. 

 

 

 

2. 접근 방식 

양수 배수 방향으로만 가는 조건을 고려해서 시간을 많이 썼다. 징검다리에는 양수의 배수 방향과 음수의 배수 방향 둘 다 올 수 있다는 점을 고려해야 한다. DFS가 아닌 BFS를 활용하는 이유는 q에 이동할 수 있는 곳의 징검다리를 넣어줘야 한다. 만약 DFS로 돌린다면 1번만에 갈 수 있는 거리를 더 많은 점프로 갈지도 모른다.

 

 

 

3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, a, b;
    static int[] visit;
    static int[] arr;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    static void input() throws IOException {
        N = Integer.parseInt(br.readLine());

        visit = new int[N];
        Arrays.fill(visit, -1);
        arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken()); b = Integer.parseInt(st.nextToken());

    }
    static int rec_func() {
        Queue<Integer> q = new LinkedList<>();
        q.add(a-1);
        visit[a-1] = 0;
        while (!q.isEmpty()) {
            int x = q.poll();
            for(int i = x; i < N; i += arr[x]) {
                if (visit[i] == -1) {
                    q.add(i);
                    visit[i] = visit[x] + 1;
                    if(i == b-1) return visit[i];
                }
            }
            for(int i = x; i >= 0; i -= arr[x]) {
                if (visit[i] == -1) {
                    q.add(i);
                    visit[i] = visit[x] + 1;
                    if(i == b-1) return visit[i];
                }
            }
        }
        return -1;

    }
    public static void main(String[] args) throws IOException{
        input();
        int ans = rec_func();
        System.out.println(ans);
    }
}

 

4. 분석 및 시간복잡도 

시간복잡도 : O(V+E)