[백준/C++] 15558번 점프 게임

백준

 

 

💡첫번째 아이디어

일단 보자마자 BFS임을 알았다! 일단 갈 수 있는데는 다 가보는데 안되면 끝인거니까

간단하게 map이라는 2차원 배열을 사용하여 두개의 지도를 표현해 주었고, BFS의 큐에는 몇초가 지났는지를 의미하는 cnt, 현재 지도의 위치를 나타내는 idx, 어떤 지도인지를 나타내주는 map_num의 정보를 담고 있는 pair 형태로 구성해주었다.

간단하게 +1, -1, 반대편 +k이므로 해당 지도의 값이 1이고, 사라지지 않은 idx일 경우에 큐에 넣어주고 idx가 n보다 커졌을 때 1을 출력하고 그렇지 않고 큐가 다 비게 되면 0을 출력한다.

 

❌첫번째 제출(4%에서 틀렸습니다)

예제 출력은 잘 나왔는데 제출해보니 틀렸다고 떴다. 문제를 다시 읽어보니 지도에서 먼저 이동하고 cnt가 커지는 방식이라 일단 cnt++를 if문 안에 넣는 방식으로 해결하려 했다. 그리고 어떻게 진행되어야 하는지 써본 결과 +1과 -1이 계속 반복되어 큐가 empty가 될 수 없을거라 판단하여 큐에 front_back이라고 해서 +1이 되어 현재 위치인 경우 다음엔 -1을 하지 않게끔 해주었다. 그리고 map_num의 값이 0과 1만 나와야 하는데 %2로는 해결할 수 없어 그냥 if문으로 케이스를 나눠주었다. 

 

❌두번째 제출(4%에서 틀렸습니다)

원래 cnt가 제대로 되어있었는데 바꾸었고 front_back만으로는 해결하지 못했다. 다시 문제를 보니 조건에 N과 k가 100000보다 작거나 같을 수 있는데 이 지도를 벗어났을 때 1을 출력해줘야 하므로 최악의 경우 지도의 맨 끝에서 +k를 했을 때 지도를 벗어날거라고 생각해서 알아낸 기쁨에 무작정 배열의 크기를 10배로 늘려주었다.

 

❌세번째 제출(메모리초과)

배열을 너무 많이 늘린 탓인지 메모리 초과가 떴다. 이번엔 마음을 가다듬고 10배가 아니라 2배로만 늘려주었다.

 

❌네번째 제출(메모리초과)

그렇게 해도 메모리 초과가 떴다. map[3][200001]에서 필요없는 마지막 줄을 빼서 map[2][200001]로 바꿔주었다. 

 

❌다섯번째 제출(메모리초과)

역시나 메모리초과 ㅠwhile문에서 메모리초과가 뜨는게 확실한거 같았다. 다시 생각해보니 cnt가 계속 늘어나서 결국엔 empty가 되므로 front_back이 굳이 필요할거 같지 않다고 판단해서 빼버렸다.

 

❌여섯번째 제출(메모리초과)

점점 메모리초과에 지쳐갔다...대체 뭐가 문제지 했는데 BFS의 근본 visited가 없었다! 생각해보면 방문처리를 해줘도 되는 문제였던 것이다!!

 

❌일곱번째 제출(틀렸습니다)

대체 뭐가 문젤까🙄 다음날 9시 근로 출근이라 일찍 자려고 했기에 내일 풀까 하다가 진짜 마지막이라는 생각으로 디버깅을 돌려봤다. 디버깅 상에는 문제가 없었다. 그때 내가 첫번째 제출에서 cnt++의 위치를 바꿔준 것이 생각났다!! 진짜 디버깅 끝나고 바로 생각남!!!암튼 조급함을 가라앉히고 다시 cnt에 대해 생각해보니 첫 제출에 제대로 해줬던 거였다. 그래서 첫 제출 때처럼 cnt++의 위치를 바꿔주고 다시 제출 ㅎ

 

⭕️여덟번째 제출(맞았습니다!!)

인간승리✌️문제 자체는 참 쉬웠는데 구현에서 이렇게 발목이 잡힐 줄 몰랐다. BFS DFS 문제를 너무 오랜만에 풀어서 그런가 기본적인 것도 빠뜨린거 같아서 조금 부끄러웠다. 그래도 12시 전에 풀고 GitHub에 push해줘서 나의 소중한 초록 잔디를 하나 더 심어줄 수 있었다. 

 

 

 

나의 수많은 도전들

맞았습니다!!

 

중간 중간 고쳐댄 탓에 깔끔해 보이진 않지만 정답이 뜬 코드이다.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int n, k;
int map[2][200001];
bool visited[2][200001];
queue<pair<int, pair<int,int>>> q;//{cnt, idx, map1인지 map2인지}


void BFS(){
    while(!q.empty()){
        int cnt = q.front().first;
        int idx = q.front().second.first;
        int map_num = q.front().second.second;
        q.pop();
        if( idx >= n ){
            cout << 1;
            return;
        }
        cnt++;
        if (map[map_num][idx+1] == 1 && (idx+1) >= cnt  && !visited[map_num][idx+1]){
            visited[map_num][idx+1] = true;
            q.push({ cnt, {idx+1, map_num}});
        }
        if( map[map_num][idx-1] == 1 &&(idx-1) >= cnt && !visited[map_num][idx-1]) {
            visited[map_num][idx-1] = true;
            q.push({ cnt, {idx-1, map_num}});
        }
        if(map_num == 0) {
            map_num = 1;
        }
        else map_num = 0;
        if( map[map_num][idx+k] ==1 && idx+k >= cnt&& !visited[map_num][idx+k]) {visited[map_num][idx+k] = true;
            q.push({cnt, {idx+k, map_num}});
        }
    }
    cout << 0;
}

int main (){
    cin.tie(NULL); ios::sync_with_stdio(false);
    cin >> n >> k;
    for(int i=0; i< n+k; i++){
        map[0][i] = 1;
        map[1][i] = 1;
    }
    string str;
    cin >> str;
    for(int i=0; i < n; i ++){
        map[0][i] = str[i]-'0';
    }
    cin >> str;
    for(int i=0; i < n; i ++){
        map[1][i] =str[i] -'0';
    }
    q.push({ 0, {0,0}});
    BFS();

}