[자바] 백준 1326 - 폴짝폴짝 (java)

목차

문제 : boj1326

 

 

필요 알고리즘

• BFS (너비 우선 탐색)
  
  • 각 징검다리에서 이동할 수 있는 모든 곳으로 이동하며 BFS를 진행해서 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  BFS를 모른다면 'BFS 알고리즘 (너비 우선 탐색)' 글을 참고해보자.

일단 맞왜틀을 외치고 있다면, 나처럼 국어 이슈일 수 있다. "징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳" 이 문장에 대해 난 당연히 배수니깐 x, x+n, x+2n, ... 이렇게 생각했는데, '배수만큼 떨어져 있는' 이므로, ..., x-2n, x-n, x+n, x+2n,... 처럼 음수 방향으로도 가능하다 ㅠ.. 이것때매 맞왜틀을 많이 외쳤다.

 

  (0, N] 이내의 범위에 대해 현재위치를 x, x위치에 써있는 정수가 n이라고 하면 .., x-2n, x-n, x+n, x+2n,...  로 움직일 수 있다. 따라서 매번 저 범위에 대해 BFS로 진행해주면 된다. 물론 이전에 이미 왔던 곳이라면 안가도 된다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
    private static final int LIMIT = 10000;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) arr[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        if (a == b) {
            System.out.println(0);
            return;
        }

        boolean[] v = new boolean[LIMIT+1];
        Queue<int[]> q = new ArrayDeque<>();
        v[a] = true;
        q.add(new int[]{a, 0});
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int num = arr[cur[0]];
            int next = cur[0];

            while (true) {
                next += num;
                if (next > n) break;
                if (v[next]) continue;
                v[next] = true;

                if (next == b) {
                    System.out.println(cur[1] + 1);
                    return;
                }
                q.add(new int[]{next, cur[1]+1});
            }

            next = cur[0];
            while (true) {
                next -= num;
                if (next < 1) break;
                if (v[next]) continue;
                v[next] = true;

                if (next == b) {
                    System.out.println(cur[1] + 1);
                    return;
                }

                q.add(new int[]{next, cur[1]+1});
            }

        }
        System.out.println(-1);
    }
}