[백준] 1326번 : 폴짝폴짝

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

1326번: 폴짝폴짝

 

문제

 

입력

 

출력

 

--

소스코드

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

public class Main {
    static int n, a, b, min = Integer.MAX_VALUE;
    static int arr[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1];
        visited = new boolean[n + 1];

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

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

        bfs();

        if(min == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(min);
    }

    static boolean visited[];
    static void bfs() {
        Deque<int[]> q = new ArrayDeque<>();
        q.addLast(new int[]{a,0});

        while(!q.isEmpty()) {
            int cur[] = q.pollFirst();

            if(cur[0] == b) {
                min = Math.min(min, cur[1]);
                return;
            }

            int stack;
            int i = 1;
            while(true) {
                stack = 0;
                int nx1 = cur[0] + arr[cur[0]] * i;
                int nx2 = cur[0] - arr[cur[0]] * i;

                if(nx1 <= n) { //오른쪽 이동
                    visited[nx1] = true;
                    q.addLast(new int[]{nx1, cur[1] + 1});
                    visited[nx1] = false;
                } else stack++;
                if(nx2 > 0) { //왼쪽 이동
                    visited[nx2] = true;
                    q.addLast(new int[]{nx2, cur[1] + 1});
                    visited[nx2] = false;
                } else stack++;

                //오른쪽, 왼쪽 둘다 이동할 수 없을 경우
                if(stack == 2) break;
                i++;
            }
        }
    }
}

 

해결 방법

1. BFS를 사용하여 a번째 징검다리에서 b번째 징검다리로 갈 수 있는 모든 경우를 탐색했다.

2. 이때, 징검다리에 쓰여있는 배수만큼 이동가능하므로 a번째 위치에서 왼쪽, 오른쪽 둘 다 탐색할 수 있음을 주의해야 한다.

2. visited[]을 두어 이미 방문한 징검다리에 재방문하지 않도록 하였다.