https://www.acmicpc.net/problem/1326
개구리가 일렬로 놓여 있는 징검다리 사이를 뛰어다니고 있다. 징검다리에는 숫자가 각각 쓰여 있고, 이 개구리가 어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다. 개구리가 a번째 징검다리에서 b번째 징검다리로 가려고 할 때, 최소 몇 번 점프를 해야 하는지 구하는 문제다.
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
ex. 가능한 시간 복잡도, 알고리즘 선택
입출력 제한
- 1 ≤ a,b ≤ N ≤ 10,000
- 1 ≤ 징검다리에 쓰여 있는 정수 ≤ 10,000
개구리가 앞으로만 점프할 수 있다고 쓰여 있지 않으므로 뒤로 점프하는 상황도 고려해야 한다. 처음엔 징검다리 정보를 입력받을 때마다 해당 징검다리에서 점프해 도달할 수 있는 모든 곳에 양방향 간선을 만들고, 너비 우선 탐색을 하려고 했는데 반례를 찾기가 어려워서 알고리즘 전체를 수정했다.
- 이전 알고리즘에서 간선을 추가할 때 양방향 대신 앞과 뒤로 각각 이동하는 것으로 수정했는데 정답 처리가 됐다. 근데 바꾼 알고리즘보다 훨씬 비효율적이어서 문제에 잘못 접근한 것 같기도 하다.
너비 우선 탐색 함수를 만들어 queue에 현재 방문한 징검다리 위치를 넣고 앞과 뒤로 각각 이동하며 다른 징검다리에 방문해 이동 거리와 방문 표시를 해야 한다. 한 번 방문한 징검다리는 다시 방문할 필요가 없다는 걸 고려해야 한다. 이동하다가 b번째 징검다리에 방문하게 되면 최소 점프 횟수를 갱신하면서 진행하면 된다.
코드 설계하기
위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!
- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지
- N, 징검다리 정보, a, b 입력받기
- a와 b가 같다면 0을 출력하고 프로그램 종료
- 다르다면 너비 우선 탐색 함수를 통해 a번째 징검다리에서 b번째 징검다리로 가는 최소 점프 횟수를 구해 출력하기
- 앞으로 이동하는 반복문과 뒤로 이동하는 반복문으로 나눠 이동
- 방문한 적이 없다면 queue에 추가하면서 이동 거리 및 방문 기록 & 방문한 곳이 b번째 징검다리라면 최소 점프 횟수 갱신
- a번째 징검다리에서 b번째 징검다리로 갈 수 없다면 -1 출력
시도 회차 수정 사항 (Optional)
- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!
1~2회차
- a와 b가 같을 때 0을 출력하고 프로그램을 종료하도록 수정함
- 처음엔 징검다리 정보를 입력받을 때마다 그래프처럼 양방향 간선을 잇고 너비 우선 탐색을 통해 b번째 징검다리에 최소로 접근할 수 있는 경우를 구하려고 했지만 알고리즘을 수정함
더보기
#include <iostream>
#include <vector>
#include <queue>
#define pii pair<int,int>
using namespace std;
int n,x,a,b,ans=1e9;
vector<int> edge[10001];
bool visit[10001];
void bfs(int st, int en) {
queue<pii> q;
q.push({st,0});
visit[st] = true;
while (!q.empty()) {
auto [x,y] = q.front();
q.pop();
for (auto i:edge[x]) {
if (i==en) ans = min(ans,y+1);
if (visit[i]) continue;
q.push({i,y+1});
visit[i] = true;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i=1; i<=n; i++) {
cin >> x;
for (int j=1; ; j++) {
int tmp = i+x*j;
if (tmp>n) break;
edge[i].push_back(tmp);
edge[tmp].push_back(i);
}
}
cin >> a >> b;
if (a==b) {
cout << 0;
return 0;
}
bfs(a,b);
if (ans==1e9) ans = -1;
cout << ans;
}- 위의 알고리즘에서 양방향 간선을 추가하는 대신 앞과 뒤로 이동하는 간선만 추가했더니 정답 처리가 되긴 했지만 메모리와 시간이 비효율적으로 나옴 → 메모리(3772KB) & 시간(4ms)
더보기
#include <iostream>
#include <vector>
#include <queue>
#define pii pair<int,int>
using namespace std;
int n,x,a,b,ans=1e9;
vector<int> edge[10001];
bool visit[10001];
void bfs(int st, int en) {
queue<pii> q;
q.push({st,0});
visit[st] = true;
while (!q.empty()) {
auto [x,y] = q.front();
q.pop();
for (auto i:edge[x]) {
if (i==en) ans = min(ans,y+1);
if (visit[i]) continue;
q.push({i,y+1});
visit[i] = true;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i=1; i<=n; i++) {
cin >> x;
for (int j=1; ; j++) {
int fr = i+x*j;
if (fr>n) break;
edge[i].push_back(fr);
}
for (int j=1; ; j++) {
int ba = i-x*j;
if (ba<1) break;
edge[i].push_back(ba);
}
}
cin >> a >> b;
if (a==b) {
cout << 0;
return 0;
}
bfs(a,b);
if (ans==1e9) ans = -1;
cout << ans;
}
정답 코드
#include <iostream>
#include <vector>
#include <queue>
#define pii pair<int,int>
using namespace std;
int n,arr[10001],a,b,ans=1e9;
bool visit[10001];
void bfs(int st, int en) {
queue<pii> q;
q.push({st,0});
visit[st] = true;
while (!q.empty()) {
auto [x,y] = q.front();
q.pop();
for (int i=x+arr[x]; i<=n; i+=arr[x]) {
if (visit[i]) continue;
if (i==en) ans = min(ans,y+1);
q.push({i,y+1});
visit[i] = true;
}
for (int i=x-arr[x]; i>=1; i-=arr[x]) {
if (visit[i]) continue;
if (i==en) ans = min(ans,y+1);
q.push({i,y+1});
visit[i] = true;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i=1; i<=n; i++) cin >> arr[i];
cin >> a >> b;
if (a==b) {
cout << 0;
return 0;
}
bfs(a,b);
if (ans==1e9) ans = -1;
cout << ans;
}