백준 1326 - 폴짝폴짝(자바 - 그래프)

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

1326번: 폴짝폴짝

 

* 문제 요약

개구리가 일렬로 놓여 있는 징검다리 사이를 폴짝폴짝 뛰어다니고 있다. 징검다리에는 숫자가 각각 쓰여있는데, 이 개구리는 매우 특이한 개구리여서 어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.

이 개구리는 a번째 징검다리에서 b번째 징검다리까지 가려고 한다. 이 개구리가 a번째 징검다리에서 시작하여 최소 몇 번 점프를 하여 b번째 징검다리까지 갈 수 있는지를 알아보는 프로그램을 작성하시오.

 

* 입력

첫째 줄에 징검다리의 갯수 N (1 <= N <= 10,000) 이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다.

그 다음줄에는 N보다 작거나 같은 자연수 a, b 가 주어지는데, 이는 개구리가 a번 징검다리에서 시작하여 b번 징검다리에 가고 싶다는 뜻이다. 징검다리에 쓰여있는 정수는 10,000 보다 작거나 같은 자연수이다.

 

* 출력

첫째 줄에 개구리가 a번 징검다리에서 b번 징검다리로 최소 몇 번 점프하여 갈 수 있는지를 출력하시오. a에서 b로 갈 수 없는 경우에는 -1 을 출력한다.

 

* 예시

 

* 해결 과정

Frog 클래스를 통해 개구리 객체를 생성한다. 이 객체는 index, jump 필드를 가지고 있는데 index 는 현재 개구리가 징검다리 상에서 위치해있는 곳을 나타내며 jump 는 개구리가 현재 위치로 오기까지 몇 번 점프를 했는지를 나타낸다.

a b 가 입력으로 들어왔을 때 b가 반드시 a보다 크다는 보장이 없으므로 개구리가 현재 위치 a에서 오른쪽으로 이동하는 경우, 현재 위치 a에서 왼쪽으로 이동하는 경우, 총 두 가지 경우를 나누어서 탐색을 진행해야 한다.

 

- 초기 객체 Frog 를 생성하면서 index 에는 a값을 저장하고 jump 에는 아직 점프를 하지 않았으므로 0 을 저장한다.

- 방문이 필요한 징검다리를 나타내는 큐 needVisit 을 만들고 해당 큐에 앞에서 만든 Frog 객체를 넣는다.

- 목적지 b까지 가는데 필요한 점프 횟수를 나타내는 변수 minJump 을 int 타입 최대값으로 초기화 시켜준 다음 아래와 같이 반복을 수행한다.

1. needVisit 큐가 비어있지 않은 경우 다음과 같이 반복을 수행한다.

2. needVisit 큐에서 가장 앞에 있는 데이터를 꺼낸 후 징검다리의 특정 위치 방문여부를 나타내는 visited 배열에서 해당 객체의 index 위치의 값을 true 로 변경하여 방문 표시를 해준다.

3. 만약 방문 필요 큐에서 꺼낸 객체의 index 위치가 도착해야 할 위치 b와 일치한다면 현재 객체의 jump 값과 minJump 값을 비교하여 minJump 값이 더 큰 경우 minJump 값을 현재 객체의 jump 값으로 초기화해준 다음 반복문을 강제로 종료한다.

4. 만약 방문 필요 큐에서 꺼낸 객체의 index 위치가 도착해야할 위치 b와 일치하지 않는다면 특정 징검다리 번호에 대해 배수를 구해주기 위한 변수 multiple 을 선언하고 1로 초기화 해준 다음 현재 위치에서 오른쪽으로 가는 경우, 왼쪽으로 가는 경우 각각에 대해 반복문을 수행해준다.

5. 현재 객체의 위치에서 오른쪽으로 향하는 경우

  - 현재 객체의 위치 (now.index) + (현재 객체가 위치해 있는 징검다리의 번호 (bridge[now.index]) * 배수(multiple)) 계산값이 징검다리 갯수 count 보다 크거나 같은 경우 반복문을 종료한다.

  - 그렇지 않을 경우 visited 배열에서 위의 계산 결과에 해당하는 인덱스 위치를 확인하고, 아직 방문하지 않은 위치일 경우 다음으로 이동할 위치에 대한 객체를 다음과 같이 생성해준다.

  - Frog next = new Frog(now. index + bridge[now.index] * multiple, now.jump + 1);

  위와 같이 생성된 객체를 방문 필요 큐 needVisit 에 저장해준다.

  - 위의 처리가 끝나고 나면 현재 위치해 있는 징검다리 번호의 추가적인 배수를 구해주기 위해 multiple 변수의 값을 1 증가시킨다.

6. 오른쪽으로 향하는 경우에 대한 반복문이 끝나고 나면 multiple 변수를 다시 1로 초기화 해주고 현재 위치에서 왼쪽으로 향하는 경우에 대한 반복문을 수행해준다.

  - 현재 객체의 위치 (now.index) - (현재 객체가 위치해 있는 징검다리 번호(bridge[now.index]) * 배수(multiple)) 계산값이 0 보다 작은 경우 반복문을 종료한다.

  - 그렇지 않을 경우 visited 배열에서 위의 계산 결과값에 해당하는 인덱스 위치를 확인하고, 아직 방문하지 않은 위치일 경우 아래와 같은 객체를 생성해준다.

  - Frog next = new Frog(now.index - bridge[now.index] * multiple, now.jump + 1);

  - 위와 같이 생성한 객체를 방문 필요 큐 needVisit 에 저장해준다.

  - 위의 처리가 끝나고 나면 현재 위치해 있는 징검다리 번호의 추가적인 배수를 구해주기 위해 multiple 변수의 값을 1 증가시켜준다.

7. 방문 필요 큐가 완전히 비어있게 되거나, 중간에 목표지점에 도착하게 되어 반복문이 종료될 경우 minJump 변수 값을 반환시켜 준다.

8. 만약 반환 받은 minJump 값이 int 타입 최대값과 일치한다면. 즉, 오른쪽 왼쪽 어느 방향으로가도 목적지에 도달하지 못했다면 -1 을 출력해준다.

9. 그렇지 않을 경우 minJump 값을 출력시켜 준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    static int[] bridge;
    static boolean[] visited;
    static int count;
    static int start;
    static int end;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        count = Integer.parseInt(br.readLine());
        bridge = new int[count];
        visited = new boolean[count]; // 방문여부 확인

        String[] inputArray = br.readLine().split(" ");
        for(int i = 0; i < inputArray.length; i++){
            bridge[i] = Integer.parseInt(inputArray[i]);
        }

        String[] startEnd = br.readLine().split(" ");

        start = Integer.parseInt(startEnd[0])-1;
        end = Integer.parseInt(startEnd[1])-1;

        int minJump = bfs();

        if(minJump == Integer.MAX_VALUE) {
            bw.write(-1 + "\n");
        }
        else{
            bw.write(minJump + "\n");
        }

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

    private static int bfs() {

        Frog frog = new Frog(start, 0);
        Queue<Frog> needVisit = new LinkedList<>();
        needVisit.add(frog);

        int minJump = Integer.MAX_VALUE;

        while(!needVisit.isEmpty()){
            Frog now = needVisit.poll();
            visited[now.index] = true;

            if(now.index == end){
                if(now.jump < minJump){
                    minJump = now.jump;
                }

                break;
            }

            int multiple = 1;

            // 오른쪽으로 이동하는 경우
            while(true){
                if(now.index + bridge[now.index] * multiple >= count){
                    break;
                }
                if(!visited[now.index + bridge[now.index] * multiple]){
                    Frog next = new Frog(now.index + bridge[now.index] * multiple, now.jump + 1);
                    needVisit.add(next);
                }
                multiple++;
            }

            multiple = 1;

            // 왼쪽으로 이동하는 경우
            while(true){
                if(now.index - bridge[now.index] * multiple < 0){
                    break;
                }
                if(!visited[now.index - bridge[now.index] * multiple]){
                    Frog next = new Frog(now.index - bridge[now.index] * multiple, now.jump + 1);
                    needVisit.add(next);
                }
                multiple++;
            }
        }

        return minJump;
    }
}

class Frog {
    int index;
    int jump;

    public Frog(int index, int jump){
        this.index = index;
        this.jump = jump;
    }
}

 

전개과정을 자세히 살펴보면 현재 위치해 있는 징검다리의 번호의 배수 만큼 떨어져 있는 거리에 있는 징검다리와 서로 연결하고, 점프 횟수를 늘려가며 해당 위치를 찾아가는 방식으로 문제를 풀었다.

조건을 만족하는 징검다리들 끼리 연결을 시켜가며 첫 시작지점 a에서 목적지 b로 가기 위한 최소한의 점프 횟수를 구했으므로 그래프 탐색 문제에 해당된다.