백준 1326번 폴짝폴짝(Java)

1326번 폴짝폴짝 (Java)

문제

난이도

• Silver 2

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

1. 현재 위치에서 갈 수 있는 징검다리 선택
2. 다음 징검다리 방문 여부 확인
3. 방문이 안된 경우 방문 체크, 몇 번째 방문인지 기록

현재 위치 기준 배수만큼 이동 가능(좌우로 이동 가능)

코드

// 백준, 1326번, 폴짝폴짝, 실버2
// https://www.acmicpc.net/problem/1326
public class Main {

    private static int N;
    private static int start;
    private static int end;
    private static int[] arr;
    private static int answer;

    public static void main(String[] args) throws Exception {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(in.readLine());

        arr = new int[N + 1]; // 1번 인덱스 부터 사용

        StringTokenizer st = new StringTokenizer(in.readLine());

        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(in.readLine());

        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
        answer = -1;

        bfs(start); // 너비 우선 탐색

        sb.append(answer);
        out.write(sb.toString());
        out.close();
    }

    private static void bfs(int a) {

        Queue<Integer> queue = new ArrayDeque<Integer>();

        int[] cnt = new int[N + 1]; // 몇 번째 방문인지 기록
        boolean[] visited = new boolean[N + 1]; // 방문여부
        visited[a]= true; 

        queue.offer(a);

        while (!queue.isEmpty()) {
            int current = queue.poll();

            if (visited[end]) {
                answer = cnt[end];
                return;
            }

            // 오른쪽 이동
            for (int i = 1; i <= N; i++) {
                int right = current + (arr[current] * i);

                if(right > N) {
                    break;
                }

                if (!visited[right]) {                    
                    cnt[right] = cnt[current] + 1;
                    visited[right] = true;
                    queue.offer(right);
                }

            }

            // 왼쪽 이동
            for (int i = 1; i <= N; i++) {
                int left = current - (arr[current] * i);

                if(left < 1) {
                    break;

                if (!visited[left]) {                    
                    cnt[left] = cnt[current] + 1;
                    visited[left] = true;
                    queue.offer(left);
                }

            }
        }

    }
}