[실버2] 11060. 점프 점프 (Java)

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

11060번: 점프 점프

점프점프,,

---

※  문제를 요약하면 아래와 같습니다.

▶ 1 X N 크기의 미로에 재환이가 갇혀서 N-1번째 포인트까지 도달해야함

▶ 각 미로 칸에는 이동 가능한 거리가 적혀있으며 N-1번까지 최소 경우로 도달

▶ N-1번에 도착 불가시 -1 출력

▶  Input : 첫째줄에 미로의 크기 N, 둘째줄에는 공백을 기준으로 각 미로칸의 값이 입력

▶  Output : 최소 경우의 수 출력, 불가능할 경우 -1 출력

---

◈ Input - 1

10
1 2 0 1 3 2 1 5 4 2

◈ Output - 1

5

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 인덱스를 노드 번호로, 해당 칸에서 가는 곳이 가능한 곳을 간선으로 연결 가능

     ex) Input-1

▶ 각 노드의 정보를 Jumper 클래스로 Point와 Count를 저장

▶ BFS 활용하여 최소 경로 탐색

---

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

class Jumper {
	int nPoint;
	int nCount;
	public Jumper(int nPoint, int nCount) {
		super();
		this.nPoint = nPoint;
		this.nCount = nCount;
	}
	
}

public class Main {
	static int[] narrMaze;
	static int[] narrDP;
	static boolean[] barrVisited;
	static int nMin;
	public static void main(String[] args) throws IOException {
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(bReader.readLine()); // 정점의 개수
		StringTokenizer st = new StringTokenizer(bReader.readLine());
		
		narrMaze = new int[N];
		narrDP = new int[N];
		barrVisited = new boolean[N];
		Arrays.fill(narrDP, Integer.MAX_VALUE);
		nMin = Integer.MAX_VALUE;
		
		for(int i = 0 ; i < N; i++) 
			narrMaze[i] = Integer.parseInt(st.nextToken());
		
		if(N== 1)
			bWriter.write("0");
		else
			bWriter.write(String.valueOf(BFS()));

		bWriter.flush();
		bWriter.close();
	}
	
	private static int BFS() {
		// TODO Auto-generated method stub
		Queue<Jumper> queueBFS = new LinkedList<Jumper>();
		queueBFS.add(new Jumper(0, 0));
		
		while(!queueBFS.isEmpty()) {
			Jumper jumper = queueBFS.poll();
			
			if(jumper.nPoint > narrMaze.length-1)
				continue;

			for(int i = 1 ; i <= narrMaze[jumper.nPoint]; i++) {
				
				
				// 배열 크기 예외처리
				if(jumper.nPoint + i > narrMaze.length-1)
					continue;
				int nNextPoint = jumper.nPoint + i;
				
				if(nNextPoint == narrMaze.length-1) {
					if(nMin > jumper.nCount+1)
						nMin = jumper.nCount+1;
				}
				// 
				if(nNextPoint > narrMaze.length-1)
					continue;
				
//				// DP 최소 경로만
//				if(narrDP[nNextPoint] >= jumper.nCount+1)
//					narrDP[nNextPoint] = jumper.nCount+1;
//				else
//					continue;
				
				
				// 방문처리
				if(barrVisited[nNextPoint])
					continue;
				else
					barrVisited[nNextPoint] = true;
				
				queueBFS.add(new Jumper(nNextPoint, jumper.nCount+1));
				
			}
	
		}
		
		if(nMin == Integer.MAX_VALUE)
			nMin = -1;
		
		return nMin;
	}

	
}

---

 

Good Luck! (피드백 감사합니다!)