본문 바로가기
PS/BOJ

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

by Nahwasa 2023. 3. 9.

목차

    문제 : 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);
        }
    }

     

    댓글