Baekjoon 11060 점프 점프 JAVA

11060번: 점프 점프

문제

해당 문제는 1차원 배열이 주어졌을 때 왼쪽 끝(0)에서 시작해서 오른쪽 끝까지 이동하는 횟수를 구하는 문제다.

조건

이동은 배열 안에 적혀있는 수만큼 이동 가능하다. 즉 3이 적혀있다면 1칸, 2칸, 3칸 이동 가능하다.

오른쪽 끝으로 이동할 수 없을 경우 -1을 출력한다.

풀이

해당 문제를 보고 bfs 또는 dp를 이용하면 해결이 가능할 것 같다고 생각했고, 알고리즘 문제를 오랜만에 해결하기 때문에 bfs를 사용해보았는데, 쉽다고 생각했는데 처음에 쫌 헤맸던 거 같다. 다시 알고리즘 공부를 틈틈이 해야겠다.

 

먼저 bfs를 사용하기 위한 작업들을 진행하고, 이후 처음 시작 위치와, 이동 횟수를 큐에 넣어준 뒤 처음 시작점을 방문 처리해주고 bfs를 시작한다.

bfs에서는 큐가 빌 때까지 반복하며 큐에서 빼낸 값의 위치 값이 오른쪽 끝일 경우 빼낸 값의 이동 횟수를 출력해주고 종료해준다. 그렇지 않다면 반복문을 도는데 여기서 해당 위치의 숫자만큼 반복하면서 이동 가능한 칸들을 모두 이동해서 이미 방문했는지 배열 범위를 벗어나는지 체크하고 그렇지 않으면 큐에 넣어주는 방식으로 로직을 구현했다.

 

만약 위의 조건에서 출력과 종료가 이루어지지 않으면 -1을 출력하는 로직을 추가해서 이동하지 못하는 경우도 처리해 주었다.

 

큐에는 현재 위치와 이동한 횟수를 저장하기 위해 클래스를 통해 데이터를 처리해주었다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, arr[]; // 전체 길이와, 각각의 값을 저장
	static boolean visit[]; // 방문 체크
	static Queue<Node> q = new LinkedList<>(); // bfs
	
	public static void main(String[] args) throws Exception{
		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());
		}
		q.offer(new Node(0,0)); // 시작위치와, 이동 횟수를 처음에 넣어줌
		visit[0] = true;
		bfs();
	}
	
	private static void bfs() {
		while(!q.isEmpty()) {
			Node n = q.poll();
			if(n.x == N-1) { // 현재 큐에서 빼온값이 오른쪽 끝지점인지 체크
				System.out.println(n.cnt);
				return;
			}
			for (int i = 1; i <= arr[n.x]; i++) { // 반복문을 1~이동할수 있는 위치까지 반복하면서 이동시킴
				int nx = n.x + i;
				if(nx >= N || visit[nx]) // 이미 방문했거나 범위 벗어나는 경우
					continue;
				q.offer(new Node(nx,n.cnt+1)); // 큐에 이동한 위치와 이동 카운트를 1증가시켜 넣어줌
				visit[nx] = true;
			}
		}
		System.out.println(-1); // 여기에 왔다면 위에서 리턴하지 못한 경우 즉 오른쪽 끝에 도착하지 못한경우
	}

	static class Node{ // 현재 위치와, 이동 수를 저장
		int x, cnt;
		Node(int x, int cnt){
			this.x = x;
			this.cnt = cnt;
		}
	}
}

 

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드