[c++] 15558 점프게임

 

오 요번꺼는 좀 귀엽다ㅋㅋㅋ

 

 

 

❔ 문제 요약

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

 

• 총 2줄의 N칸짜리 보드가 주어진다.
• 유저는 왼쪽 줄의 1번 칸에서 시작한다.
• 매 초마다 3가지 중 하나의 이동을 할 수 있다
  • 앞으로 1칸 이동
  • 뒤로 1칸 이동
  • 반대편 줄의 (현재 칸 + k)칸으로 점프
• 칸은 시간이 지나면서 사라진다 -> t초가 지나면 1~t번 칸은 사라져서 이동 불가
• N을 넘어가면 게임 클리어

 

---

🔑 해결 전략: BFS 

• 단순한 BFS처럼 보이지만, 시간 경과에 따라 칸이 사라지는 조건이 핵심
• 각 칸에 도착할 때의 시간을 저장해두고,
• 그 칸이 아직 살아있는지(시간 < 칸 번호) 확인해야 함
• 이미 더 빠르게 도달한 적 있다면 재방문하지 않음

 

💙 Step 1: 보드 설정

int B[2][MAX];   // 2줄의 보드, 1이면 안전, 0이면 위험

for (int i = 0; i < 2; i++) {
    string str; cin >> str;
    for (int j = 0; j < str.size(); j++) {
        if (str[j] == '1') B[i][j+1] = INT_MAX;  // 안전한 칸
        else B[i][j+1] = 0;                      // 위험한 칸
    }
}

안전한 칸은 1 대신 INT_MAX를 넣고, 나중에 최소 시간으로 갱신해 나감 

 

💙 Step 2: BFS 탐색  

B[0][1] = 1; // 시작점 시간 = 1
queue<pair<int,int>> q;
q.push({1,0}); // (위치 1, 줄 0)

각 위치에서 3가지 행동에 대하여 탐색

 

➡️ 앞으로 한 칸

if (B[line][pos+1] && B[line][pos+1] > B[line][pos] + 1) {
    B[line][pos+1] = B[line][pos] + 1;
    q.push({pos+1, line});
}

이동할 수 있는 칸(안전한 칸)이고, 이전보다 더 빠른 시간으로 도달하면 갱신

 

⬅️ 뒤로 한 칸

if(pos-1>=1 && B[line][pos-1]){
    if(B[line][pos-1]>B[line][pos]+1 && B[line][pos]+1<=pos-1){
        B[line][pos-1] = B[line][pos]+1;
        q.push({pos-1,line}); 
    }
}

• pos-1>=1 : 뒤로 갔을때 1보다 같거나 큰 경우만 이동 (OutOfIndex 방지)
• B[line][pos-1] : 안전한 칸인 경우만 이동
• B[line][pos-1]>B[line][pos]+1 : 갱신이 가능하고 
• B[line][pos]+1<=pos-1 : 아직 칸이 없어지지 않아서 밟을 수 있을때만 큐에 추가 

 

🔁 반대편 줄로 점프

if(B[(line+1)%2][pos+k]){ // 안전한 칸이고 
    if(B[(line+1)%2][pos+k]>B[line][pos]+1){ // 갱신이 가능하다면 
        B[(line+1)%2][pos+k]=B[line][pos]+1;
        q.push({pos+k,(line+1)%2});
    }
}

 

✅ isClear 함수

void isClear(int pos){
    if(pos > n){
        cout << 1 << '\n';
        exit(0);
    }
}

현재 위치가 n 초과면 즉시 게임 클리어 → exit(0)으로 종료

 

 

---

✅ 정답 코드 

// 15558 점프게임
// 메모리제이션 + 큐

#include<iostream>
#include<queue>
#include<climits>
#include<algorithm>
#include<string>
#define MAX 100'001
using namespace std;

int B[2][MAX];
int n;

void isClear(int pos){
    if(pos>n){
        cout<<1<<'\n';
        exit(0);
    };
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int k; cin>>n>>k; //  1 ≤ N, k ≤ 100,000
    for(int i=0,tmp;i<2;i++){
        string str; cin>>str;
        for(int j=0;j<str.size();j++){
            if(str[j]=='1')B[i][j+1]=INT_MAX; // 갈 수 있는 곳이라면 최대값으로 초기화 -> 이후 최솟값으로 갱신해 나갈것 
            else B[i][j+1]=0;
        }
    }
    B[0][1]=1; // 왼쪽 줄의 1번 칸은 항상 안전한 칸

    queue<pair<int,int>> q; // 현재 위치, 현재 줄
    q.push({1,0}); // 0번째줄 1번에서 시작 

    while(!q.empty()){
        int pos=q.front().first;
        int line=q.front().second; 
        q.pop();

        // 앞으로 한칸
        isClear(pos+1); 
        if(B[line][pos+1]){ // 0이 아닐떄(위험한 칸이 아닐 때) 수행
            if(B[line][pos+1]>B[line][pos]+1){
                B[line][pos+1] =B[line][pos]+1;
                q.push({pos+1,line});
            }
        }

        // 뒤로 한칸
        if(pos-1>=1 && B[line][pos-1]){
            if(B[line][pos-1]>B[line][pos]+1 && B[line][pos]+1<=pos-1){
                B[line][pos-1] = B[line][pos]+1;
                q.push({pos-1,line}); 
            }
        }

        // 건너편으로
        isClear(pos+k);
        if(B[(line+1)%2][pos+k]){
            if(B[(line+1)%2][pos+k]>B[line][pos]+1){
                B[(line+1)%2][pos+k]=B[line][pos]+1;
                q.push({pos+k,(line+1)%2});
            }
        }
    }
    cout<<0<<'\n';
}

 

 

---

💥 시행착오 : 메모리 초과 발생 원인과 해결

// 15558 점프게임
// 메모리제이션 + 큐

#include<iostream>
#include<queue>
#include<climits>
#include<algorithm>
#include<string>
#define MAX 100'001
using namespace std;

int B[2][MAX];
int n;

void isClear(int pos){
    if(pos>n){
        cout<<1<<'\n';
        exit(0);
    };
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // freopen("input.txt","r",stdin);

    int k; cin>>n>>k; //  1 ≤ N, k ≤ 100,000
    for(int i=0,tmp;i<2;i++){
        string str; cin>>str;
        for(int j=0;j<str.size();j++){
            if(str[j]=='1')B[i][j+1]=INT_MAX; // 갈 수 있는 곳이라면 최대값으로 초기화 -> 이후 최솟값으로 갱신해 나갈것 
            else B[i][j+1]=0;
        }
    }
    B[0][1]=1; // 왼쪽 줄의 1번 칸은 항상 안전한 칸

    queue<pair<int,int>> q; // 현재 위치, 현재 줄
    q.push({1,0}); // 0번째줄 1번에서 시작 

    while(!q.empty()){
        int pos=q.front().first;
        int line=q.front().second; 
        q.pop();

        // 앞으로 한칸
        isClear(pos+1); 
        if(B[line][pos+1]){ // 0이 아닐떄(위험한 칸이 아닐 때) 수행
            B[line][pos+1] = min(B[line][pos+1],B[line][pos]+1);
            q.push({pos+1,line});
        }

        // 뒤로 한칸
        if(pos-1>=1 && B[line][pos-1]){
            B[line][pos-1] = min(B[line][pos-1],B[line][pos]+1);
            // 아직 칸이 없어지지 않아서 밟을 수 있다면 큐에 추가 
            if(B[line][pos]+1<=pos-1) q.push({pos-1,line}); 
        }

        // 건너편으로
        isClear(pos+k);
        if(B[(line+1)%2][pos+k]){
            B[(line+1)%2][pos+k] = min(B[(line+1)%2][pos+k],B[line][pos]+1);
            q.push({pos+k,(line+1)%2});
        }
    }

    cout<<0<<'\n';
}

 

 

• 원인 : min()만 써서 무조건 큐에 추가

이렇게 하게 되면 이미 방문한 칸도 다시 큐에 넣는 상황이 발생

min()으로만 갱신하면서 더 느린 시간이어도 무조건 q.push()를 하게 되고,
동일한 칸을 여러 번 방문 → 큐의 크기가 비정상적으로 커짐 → 메모리 초과 

 

• 해결 :  조건 추가로 큐 삽입 제한

도달 시간이 더 빠를 때만 큐에 추가하도록 수정