문제 탐색하기

입력 자료 정리

1. 입력값 N은 이후 들어오는 징검다리 입력값의 개수이다
2. N만큼 들어오는 입력은 각 인덱스의 이동 배수이다
3. 다음 들어오는 두 값은 시작 지점과 끝지점이다.
4. 이때 시작지점과 끝지점의 경우 '몇 번째'로 되어있기 때문에, 인덱스를 1부터 시작할 필요가 있다.

해결방법 추론

1. 현재 위치에서 끝지점에 도달할 때까지, 적혀있는 숫자만큼의 모든 이동을 확인한다면
   쉽게 문제를 해결할 수 있겠다고 생각하였다
2. 브루트포스, DFS, BFS정도가 가능할 것이라 생각하였다
3. 일단 브루트포스와 DFS는 선택에서 제외되었는데 N의 최대 입력값이 1만이라,
   브루트포스나 DFS로는 시간초과나 메모리 초과가 발생할 수 있을 것이라 생각했기 때문이다
4. 그렇다면 BFS로는 풀 수 있을까도 고민해봤다
5. BFS로 풀게 된다면, 현재 지점에서 갈 수 있는 모든 경우를 큐에다가 넣으면서
   도착지점에 도달하는 경우를 찾게 될 것이다
6. 이때 오른쪽으로 가는 경우와 왼쪽으로 가는 경우를 모두 넣을 수 있을 것이고,
   운이 좋다면 N번만에 해결할 수 있을 것이라 생각하였다
7. 하지만 또 생각해보면, 탈출하는 경우를 못찾는 경우도 존재할 것이라 생각하였다
8. 만약 아예 목적지로 못가는 경우는 계속 같은 위치를 맴돌 수도 있을 것이다
9. 그렇기에 방문배열을 하나 더 만들어서 무한루프로
   bfs를 못 빠져나가는 경우를 막아야겠다고 생각하였다
10. 또한 문제에서 구하는 것을 최소 횟수이기 때문에 방문 배열을 사용해도 무방하다
11. 마지막으로 도착지점에 도달했을 때마다, 그 누적횟수를 비교해주어야 할까?
    아니면 최초 도착한 경우에만 정답으로 하고 종료해야할까도 고민하였다
12. 여기서 구하는 것을 최소 이동 횟수이고, BFS 탐색에서는 큐에서 꺼낼 때마다
    이동 횟수가 늘어나게 된다
13. 그렇기에 무조건 처음 도착지에 도달하는 경우만이 정답이 된다
14. 따라서 다음과 같이 생각하고 BFS를 하면 문제를 풀 수 있겠다고 생각하였다

시간복잡도 계산

1. BFS에서 시간복잡도는 어떻게 될까?
2. 보통 O(V+E)의 시간복잡도를 갖는다
3. 그렇다면 이 문제에서는 어떤 시간복잡도를 가질까?
4. BFS 탐색에서 나올 수 있는 최악의 경우를 생각해보자.
5. 시작지점과 끝지점이 양 끝에 있을때가 아마 최악의 경우가 될 것이다
6. 이때 1만큼의 배수로 이동한다고 했을 때, n만큼의 연산이 발생할 것이다
7. 따라서 O(N)이 시간복잡도가 될 것이고, 시간제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리하기

1. n과 출발지, 도착지는 변수로 관리한다
2. 징검다리는 int형 1차원 배열에 관리하며, 크기는 n+1로 한다
3. BFS탐색에서 필요한 방문배열도 똑같은 크기로 만들어준다

BFS 설계

1. n과 start, end를 인수로 넘겨주며 시작한다
2. 탐색을 위한 큐를 하나 만드는데, 타입은 int형 1차원 배열로 한다
3. 0번 인덱스에는 현재 위치를 관리할 것이며, 1번 인덱스에는 누적된 이동횟수를 넣을 것이다
4. 첫번째 방문지에 대한 방문 체크와 누적 이동횟수 0과 함께 현재 위치를 큐에 넣어준다
5. 매번 큐에서 배열을 하나 뽑아낸다음, 도착지에 도달했는지 확인한다
6. 만약 도달했다면 ans 변수에 누적된 이동횟수인 1번 인덱스의 값을 넣어주고 탐색을 종료한다
7. 이어서 징검다리에 적힌 배수를 입력값을 관리하는 배열에서 가져와 변수로 관리한다
8. 오른쪽으로 이동하는 경우와 왼쪽으로 이동하는 경우를 나눠 관리한다
9. 두 경우 모두 0번 인덱스의 값을 시작 지점으로 하며,
   인덱스 범위를 벗어나지 않도록 포문을 설정해둔다
10. 오른쪽으로 이동하는 경우는 i에 배수만큼 더하고, 왼쪽으로 이동하는 경우는 i에 배수만큼 뺀다.
11. 미방문 한경우, 방문체크 후, 큐에 넣어준다. 이때 이동횟수를 1만큼 더해서 넣어준다

출력 설계

1. BFS 탐색결과 완성된 ans를 출력한다
2. 만약 못찾는 경우가 발생한다면 -1을 출력해야하기 때문에,
   미리 ans를 -1로 초기화하여 출력한다
3. 이렇게 하면 정답이 된다.

정답 코드

(1회차 시도 성공!)

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

public class Main {


    static int[] arr;
    static int ans = -1;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        arr = new int[n+1];
        visited = new boolean[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i < n+1; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        bfs(n, start, end);

        bw.write(ans+"");


        br.close();
        bw.close();
    }

    private static void bfs(int n, int start, int end) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{start, 0});
        visited[start] = true;
        while(!q.isEmpty()){
            int[] cur = q.poll();

            if(cur[0] == end){
                ans = cur[1];
                return;
            }
            int move = arr[cur[0]];

            for (int i = cur[0]; i < n+1; i+=move) {
                if(!visited[i]){
                    visited[i] = true;
                    q.add(new int[]{i, cur[1]+1});
                }
            }

            for (int i = cur[0]; i > 0; i-=move) {
                if(!visited[i]){
                    visited[i] = true;
                    q.add(new int[]{i, cur[1]+1});
                }
            }

        }
    }

}

문제 링크

1326번 - 폴짝폴짝