[백준] 11060번 점프 점프 JAVA (자바) 풀이

문제 11060번 (bfs)

 :  1×N 크기의 미로 ( 1×1 크기의 칸으로 이루어져 있다)

    i번째 칸에 쓰여 있는 수를 Ai

 

 :  Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프가능

    (예 : 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프가능)

 

 :  현위치 = 미로의 가장 왼쪽 끝 / 가장 오른쪽 끝으로 가려고 할 때 최소 몇 번 점프를 해야하는지 구해라

    (가장 오른쪽 끝으로 갈 수 없다면 -1을 출력)

 

 

 [입력]

 :  첫째 줄에 N(1 ≤ N ≤ 1,000)

 :  둘째 줄에 Ai (0 ≤ Ai ≤ 100)

 

 

[출력]

 :  최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력

    (갈 수 없다면 -1 출력)

 

[설명]

 

1. 출력 배열 사용하지 말고 큐에다 넣어버리기

• 14940, 18352, 5014 과 같은 문제에서는 ocunt[] 배열을 사용했다 (count[next]=count[p]+1)
• 그것보다 큐 자체에 넣는 것이 더 간단하다 q.add(new int{start,0}) 추천

 

2. bfs를 for문이나 재귀에 사용하지 말 것

• for(){ bfs } 하지말 것 (bfs 메서드 내에서 큐에 계속 추가하면서 반복하면 된다)
• bfs메서드 내에서 다시 bfs를 호출하지 말 것 (백트래킹이나 dfs와는 다르다)

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N,arr[],result[];
    static boolean visit[];
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        visit = new boolean[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i =0; i<N;i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
        
        bfs(0);

    }
    
    static void bfs(int start){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{start,0});
        visit[start]=true;
        
        while(!q.isEmpty()){
            int[] p = q.poll();
            if(p[0]==(N-1)){
                System.out.println(p[1]);
                return;
            }
            for(int i =1; i<=arr[p[0]]; i++){
                int next = p[0] + i;
                if(0<=next&&next<N && !visit[next]){
                    q.add(new int[]{next,p[1]+1});
                    visit[next]=true;
                }
            }
        }
        System.out.println("-1");
    }
}

 

 [해설]
     

 :  static int N,arr[],result[];
    static boolean visit[];
   

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());  입력
    arr = new int[N];  입력 배열
    visit = new boolean[N];  방문기록
        
 :  StringTokenizer st = new StringTokenizer(br.readLine()); 
    for(int i =0; i<N;i++){  
            arr[i]=Integer.parseInt(st.nextToken());   입력받기
    }
        
 :  bfs(0);
    

 :  static void bfs(int start){
        Queue<int[]> q = new LinkedList<>();  큐선언
        q.add(new int[]{start,0});  큐에 시작노드, 카운트 추가
        visit[start]=true;  방문처리
        
        while(!q.isEmpty()){  
            int[] p = q.poll();  큐에서 뽑기
            if(p[0]==(N-1)){  노드가 N-1이라면 더 움직일 수 없으니 종료하고 
                System.out.println(p[1]);  카운트 출력
                return;
            }
            for(int i =1; i<=arr[p[0]]; i++){
                int next = p[0] + i;  현재 노드 + 갈 수 있는 만큼 이동
                if(0<=next&&next<N && !visit[next]){  접근 가능하면
                    q.add(new int[]{next,p[1]+1});  큐에 추가
                    visit[next]=true;  방문처리
                }
            }
        }
        System.out.println("-1");  마지막 노드 N-1에 접근할 수 없다면 -1 출력
   }


   

 

      

이제 풀어보러 갈께요 :)

 

 

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

 

 

 

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *