[Java] 백준 14248 점프 점프 - 실버2

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

14248번: 점프 점프

 

 

 

반례들 

(예시 입력만 돌아가면 무지성으로 제출하는 습관이 있음. 그래서 이제부터는 몇 가지 반례들을 돌려보려고 한다)

5
1 1 1 1 1
1
=> 5

3
7 1 1 
1
=> 1

5
3 1 5 2 5
1
=> 4

 

 

자바코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
  public static void main(String[] args) throws IOException {
    //입력 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int stoneCnt = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    int startIdx = Integer.parseInt(br.readLine()) - 1;

    int[] stone = new int[stoneCnt];
    for (int i=0; i<stoneCnt; i++)
      stone[i] = Integer.parseInt(st.nextToken());
    boolean[] visit = new boolean[stoneCnt];

    //시작 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
    Queue<Integer> queue = new LinkedList<>();
    int result = 0;

    //시작점을 queue에 넣기
    visit[startIdx] = true;
    queue.add(startIdx);

    while(queue.size() != 0){
      int idx = queue.poll();
      result ++;

      int move = stone[idx];
      //왼쪽
      if (idx-move >= 0 && !visit[idx-move]){
        queue.add(idx-move);
        visit[idx-move] = true;
      }

      //오른쪽
      if (idx+move < stone.length && !visit[idx+move]){
        queue.add(idx+move);
        visit[idx+move] = true;
      }
    }

    System.out.println(result);
  }
}

• 돌들의 값들과 visit배열을 만들어준다
  
  • 한 번 방문하면 visit 배열의 값을 true로 만들어주는 방식을 사용할 것이다
• 큐를 하나 만들어 시작점의 인덱스를 넣는다
• 큐가 빌 때까지 반복문을 수행한다
  • 큐에서 한 값을 꺼내고 visit값을 true로 만들고, result값을 하나 증가시켜준다
  • 해당 돌에서 왼쪽으로 점프해서 갈 수 있는 돌, 오른쪽으로 점프해서 갈 수 있는 돌의 인덱스를 큐에 넣는다