https://www.acmicpc.net/problem/11060
재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 A_i라고 했을 때, 재환이는 A_i 이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.
재환이가 지금 미로의 가장 왼쪽 끝에 있고 가장 오른쪽 끝으로 가려고 할 때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 문제다.
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
ex. 가능한 시간 복잡도, 알고리즘 선택
입출력 제한
- 1 ≤ N ≤ 1,000
- 0 ≤ A_i ≤ 100
- 가장 오른쪽 끝으로 갈 수 없는 경우엔 -1을 출력한다.
25418 - 정수 a를 k로 만들기와 비슷한 문제다. 위치별 최소 점프 횟수를 저장할 배열을 만들어 놓고 적당히 큰 값으로 초기화한다. 이후 미로의 가장 왼쪽 끝에서 너비 우선 탐색을 돌린다. 점프를 하다보면 배열의 최댓값을 넘을 수 있으므로, 배열의 최댓값을 넘지 않을 때와 최소 점프 횟수로 만들 수 있는 경우에만 queue에 넣으면서 진행해야 한다.
코드 설계하기
위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!
- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지
- N, 미로 정보 입력받기
- 각 위치별 최소 점프 횟수를 저장할 배열 초기화하기
- 미로의 가장 왼쪽 끝에서 너비 우선 탐색 돌리기
- queue에 현재 좌표와 최대 점프 거리를 pair<int,int>로 넣기
- 최소 점프 횟수를 갱신할 수 있는 경우에만 queue에 넣으면서 진행하기
- 미로의 가장 오른쪽 끝에 도달할 수 없다면 -1, 도달할 수 있다면 최소 점프 횟수 출력하기
시도 회차 수정 사항 (Optional)
- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!
pass
정답 코드
#include <iostream>
#include <queue>
#include <algorithm>
#define pii pair<int,int>
using namespace std;
int n,arr[1001],ans=1e9,visit[1001];
void bfs(int start, int jump) {
queue<pii> q;
q.push({start,jump});
visit[start] = 0;
while (!q.empty()) {
auto [cur,next_j] = q.front();
q.pop();
for (int i=1; i<=next_j; i++) {
if (cur+i<n && visit[cur+i]>visit[cur]+1) {
q.push({cur+i,arr[cur+i]});
visit[cur+i] = visit[cur] + 1;
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i=0; i<n; i++) cin >> arr[i];
fill(visit,visit+1001,1e9);
bfs(0,arr[0]);
cout << (visit[n-1]==1e9 ? -1 : visit[n-1]);
}