[Algorithm Study] 백준 11060
문제 출처 : https://www.acmicpc.net/problem/11060
문제 접근
위의 문제를 읽으면 1XN으로 이루어진 미로에 대해서 각 자리마다 정해진 수 만큼 이동이 가능합니다. 각자리에 대한 배열을 생성한 뒤에 방문순서를 기록하고 마지막 위치에 기록된 수가 0인 경우, 끝까지 도달을 못한 것으로 판단했고 그렇지 않은 경우에는 끝까지 도달한 것으로 보아 최소 점프를 횟수를 출력하도록 BFS를 활용하여 문제를 해결했습니다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[] map = new int[N];
int[] check = new int[N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++){ // 맵 생성
map[i] = Integer.parseInt(st.nextToken());
}
int index = 0;
Queue<Integer> q = new LinkedList<>();
q.offer(map[index]);
while(!q.isEmpty()){
int y = q.poll(); // 큐에서 꺼내는 것
int visit = check[index]; // 이전 값 넣기
for(int i = 0; i < y; i++){
index++;
if(index >= N){
break;
}
if(check[index] == 0){
check[index] = visit + 1;
q.offer(map[index]);
}
}
if(y == 0){
index++;
}
for(int i = 0; i < y-1; i++){
index--;
}
}
if(N == 1){
System.out.println(0);
}
else if(check[N-1] == 0){
System.out.println(-1);
}
else{
System.out.println(check[N-1]);
}
}
}
Author And Source
이 문제에 관하여([Algorithm Study] 백준 11060), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@seokhwan-an/Algorithm-Study-백준-11060저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)