[코드트리] 사다리 타기 C++

문제

https://www.codetree.ai/missions/2/problems/ladder-game?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 첫 번째 풀이🧐

Possible(vector result)

전역 변수origin_result와 매개변수로 들어온 result를 비교해 동일하다면 true 아니면 false를 출력

Make_Board()

주어진 lines벡터를 이용해 board를 1로 그리고, lines_to_remove벡터를 이용해 0으로 지우는 함수

Play()

Make_Board()함수를 불러 현재 lines_to_remove가 적용된 board를 그리고, player들을 사다리타기 시켜서 result벡터에 순서대로 저장함

FindMinLineSegments(int idx_line)

지울 선(idx_line)을 선택하는 함수

#include <iostream>
#include <vector>
#include <cstring> // memset()

using namespace std;

int n=0, m=0, answer=100;
int board[16][12];

vector<pair<int, int>> lines;
vector<pair<int, int>> lines_to_remove;
bool already_removed[16]; // visited배열. 이미 제거된 선분을 다시 방문하지 않기 위함
vector<int> origin_result;

// result의 값을 변환하거나 하지 않아서 참조로 넘기지 않아도 됨
// origin_result랑 다른 값이 있으면 false리턴
bool Possible(vector<int> result){
    //cout <<"origin'\n";
    //for(int i=0; i<(int)origin_result.size();i++){
    //    cout << origin_result[i] << " ";
    //}
    //cout <<"\nthis result\n";
    //for(int i=0; i<(int)result.size();i++){
    //    cout << result[i] << " ";
    //}
    //cout <<'\n';

    for(int i=0; i<(int)origin_result.size();i++){
        if(origin_result[i]!=result[i]) return false;
    }
    return true;
}

void Make_Board(){
    //board초기화
    memset(board, 0, sizeof(board));

    // line을 그리기
    for(int i=0; i<(int)lines.size(); i++){
        board[lines[i].first][lines[i].second]=1;
        board[lines[i].first][lines[i].second+1]=1;
    }
    // lines_to_remove에 들어있는 선 지우기
    for(int i=0; i<(int)lines_to_remove.size(); i++){
        board[lines_to_remove[i].first][lines_to_remove[i].second]=0;  
        board[lines_to_remove[i].first][lines_to_remove[i].second+1]=0;  
    }

}

vector<int> Play(){
    //board 그리기
    Make_Board();

    vector<int> result;
    result.reserve(n); //n개의 공간 확보

    // player별로 이동시키기
    for(int player=0; player<n; player++){
        int pos_x =0, pos_y=player;

        while(pos_x<16){
            // 1이면 오른쪽 왼쪽 확인해서 1인 곳으로 이동하고 아래로 한 칸 내려가기
            // 0이면 가로줄이 없다는 뜻이므로 그냥 아래로 내려가기
            if(board[pos_x][pos_y]==1){
                // 왼쪽 이동
                if(pos_y-1>=0 && board[pos_x][pos_y-1]==1){
                    pos_y--;
                }
                //오른쪽 이동
                else if(pos_y+1<n && board[pos_x][pos_y+1]==1){
                    pos_y++;
                }
            }
            pos_x++;
        }
        result[pos_y]=player;
    }
    //cout << "result\n";
    //for(int i=0; i<n; i++){
    //    cout << result[i] <<" ";
    //}
    //cout <<'\n';
    return result;
}

void FindMinLineSegments(int idx_line){
    // 종료 조건
    if(idx_line==m){
        vector<int> v = Play();
        //for(auto e : v){
        //    cout << e << " ";
        //}
        //cout <<'\n';

        // [갱신]처음과 결과가 같은데, 저장된 것보다 더 적은 선분을 이용했을 경우
        if(Possible(v)){
            int num_of_line = m-(int)lines_to_remove.size();
            if (num_of_line<answer) answer = num_of_line;
        }
        return;
    }
    // 재귀 호출
    // m개의 선 중 지워야 할 선 고르기
    for(int i=0; i<m; i++){
        if(already_removed[i]) continue;
        
        lines_to_remove.push_back({lines[i].first, lines[i].second});
        already_removed[i]=true;
        FindMinLineSegments(idx_line+1);

        lines_to_remove.pop_back();
        already_removed[i]=false;
        FindMinLineSegments(idx_line+1);
    }
}

int main() {
    cin >> n >> m;
    
    for(int i=0;i<m;i++){
        int a, b;
        cin >> a >> b;
        // 문제는 배열이 1부터 시작하기 때문에 1을 뺀 값을 적용.
        a-=1;
        b-=1;
        //board[b][a]=1;
        //board[b][a+1]=1;
        lines.push_back({b, a});
    }

    origin_result = Play();
    
    FindMinLineSegments(0);
    cout << answer;
    return 0;
}

 

문제점

Play()에서 반환한 벡터가 origin_result나 v벡터에 저장되지 않는다. Play() 안에서는 result에 값이 잘 저장되는데, origin_result=Play()를 한 후 origin_result를 출력하면 아무것도 출력이 되지 않는다.

 

해결

문제는 vector.reserve()함수에서 발생한 것이었다.

 

해결 요약

result의 size를 n으로 설정하면 해결된다.

//vector<int> result;
//result.reserve(n); //n개의 공간 확보

// 1. result(n)으로 size n으로 벡터를 초기화 해주는 방법
vector<int> result(n);

// 2. resize()를 이용하는 방법
vector<int> result2;
result2.resize(n);

// 3. reserve로 capacity를 늘린 후 n개의 요소를 직접 넣어주는 방법
vector<int> result3;
result3.reserve(n); //n개의 공간 확보
for(int i=0; i<n; i++){
	result3.push_back(0); //n개의 요소를 직접 넣어주기(size를 직접 늘려주기)
}

 

내가 reserve함수를 이용한 이유

Play() 함수에서 result의 갯수가 몇 개인지 선언해줘야 result[pos_y]=player; 라고 해당 칸에 player 번호를 저장해줄 수 있다. vector<int> result; 라고만 적으면 빈 벡터가 만들어지기 때문!

 

그래서 vector.reserve(n)을 이용하는 방법을 검색으로 알아냈다. (문제는 reserve함수가 어떤 것인지 제대로 알아보지 않고 이용했다는 것...)

 

vector.reserve()가 뭔데

vec.reserve(n)는 벡터의 capacity를 n개로 늘려달라는 의미이다. 이 동작은 capacity를 늘릴 뿐이지, size를 늘려주지는 않는다.

size vs. capacity

size는 벡터 안에 실제로 들어 있는 요소의 개수이고, capacity는 벡터에 들어갈 수 있는 최대 요소의 개수이다. 벡터에 대해 모른다면 저 말이 조금 헷갈릴 수 있다.

 

벡터는 동적 배열이다. 이를 기반에 두고, 위에 말을 좀 더 쉽게 설명해보겠다!

vector<int> vec; // size:0, capacity:0
vec.reserve(3); // size:0, capacity:3
vec.push_back(1); // size:1, capacity:3

vector<int> vec2; // size:0, capacity:0
vec2.push_back(1); // size:1 capacity:1
vec2.push_back(2); // size:2 capacity:2
vec2.push_back(3); // size:3 capacity:4

 

capacity는 메모리 같은 느낌이다. 휴대폰의 용량이 128기가라면, 128기가 만큼의 공간을 이용할 수 있다. size는 해당 공간 중 내가 실제로 이용하고 있는 부분이다.

 

128기가를 이용할 수 있는 휴대폰을 사용하고 있는데, 128기가가 전부 찼다고 생각해보자. 이때 다른 앱을 설치(push_back)하려고 하면 벡터는 어떻게 이 상황을 해결할까? 벡터는 256기가의 휴대폰을 들고와서 이전 휴대폰에 들어 있던 사진, 동영상, 앱 등을 모두 옮기고, 새로운 앱을 설치해준다.

 

위의 코드로 돌아가서 생각해보자. vec은 용량이 0인 휴대폰이다. vec.reserve(3)은 용량이 3인 휴대폰으로 변경하는 것이다. 용량이 0이었기 때문에 안에 있던 데이터의 복사는 일어나지 않는다. 하지만 용량이 3인 휴대폰으로 변경했을 뿐이고 안에 어떤 앱도 설치되지 않았다. vec.push_back(1); 을 해야 1이 설치되는 것. size는 1이 되고, capacity는 3인 상태가 된다.

 

vector.reserve()를 쓰는 이유 → 최적화!

vec2도 보자. vec2는 size가 0이고 capacity가 0인 상태이다. 이때 앱을 설치할 거야! 라고 하면 앱을 설치할 수 있도록 새 휴대폰을 마련해오고, 원래 폰에 있던 데이터를 옮긴다. 그 후 사용자가 요청했던 앱을 설치해준다(push_back(1)). vec2는 capacity가 1이고 size가 1인 휴대폰이 된다.

용량이 다 찼는데, 또 앱을 설치해달라고 한다. 앱을 설치하게는 해줘야 하니 용량이 2인 휴대폰을 마련해온다. 원래 휴대폰에 있던 1이라는 앱을 옮긴 후, 사용자가 요청한 앱을 설치해준다(push_back(2)). vec2는 size: 2, capacity: 2인 휴대폰이 되었다.

 

또!!!! 앱을 설치해달라고 해보자. 용량이 4인 휴대폰을 마련해온다. ????????? 왜 이번에는 용량이 3이 아니라 4인 휴대폰을 마련해왔는가? 위에 예시에서 128기가 휴대폰 용량이 다 찼는데 새 앱을 설치하려고 하면 256기가 휴대폰을 구해온다고 말했었다. 벡터는 현재 capacity가 부족해서 더 큰 용량을 가진 휴대폰으로 바꿀 때 보통 2배의 용량을 가진 휴대폰으로 바꾼다. 따라서 용량이 4인 휴대폰으로 바꾸고, 기존에 있던 데이터를 옮긴 후, 원하던 앱을 설치해준다(push_back(3)). vec2는 size:3 capacity:4인 휴대폰이 된 것!

 

휴대폰에 비유했으니 실제로 우리가 새 휴대폰을 바꿨다고 생각해보자. 새 휴대폰에 기존 휴대폰에 있던 데이터들을 옮길 것이다. 기존 휴대폰에 있던 앱, 사진, 동영상이 많을수록 더 오랜 시간이 걸린다. 컴퓨터에서 용량이 큰 폴더를 다른 폴더로 이동시킬 때 오래 걸린 것을 생각해보자! 용량이 크면 클수록 옮기는 데에 시간이 많이 걸린다. 따라서 휴대폰은 정해진 용량 내에서만 사용하는 것이 시간이 적게 걸린다! vector.reserve를 사용하면 용량을 미리 늘리는 것이기 때문에 휴대폰을 덜 바꿀 수 있어 시간이 절약된다! 즉, reserve를 쓰면 최적화에 도움이 된다는 이야기이다! capacity가 부족할 때 vector가 capacity가 2배인 휴대폰으로 바꾸는 이유도 이와 같다. 만약 128기가를 쓰다가 앱하나를 추가하려고 했더니 512기가 휴대폰을 들고 왔다고 생각해보자. 얘가 내 돈을 낭비할 셈인가? 라는 생각이 들 것이다. 벡터에 무작정 크게 메모리를 할당해주면 메모리 낭비가 일어날 수 있기 때문에 2배로 늘리는 것 같다.

 

 

reserve함수를 이용한 게 그래서 왜 문제인데?

result.reserve(n)는 벡터의 capacity를 n개로 늘려달라는 의미라고 했다. 이는 용량이 n인 빈 휴대폰을 가지고 있는 것과 같다. 근데 Play() 함수에서 result[pos_y]=player;라고 쓴 것이 문제가 됐다. 현재 result는 size가 0이고, capacity가 n인 벡터이다. result에는 어떤 앱이나 사진, 동영상도 없는데, pos_y번째에 있는 사진을 player라는 사진으로 바꿔달라고 요청한 것이다.

 

이는 즉, 벡터의 크기(size)를 벗어난 요청이 되는 것이다. 우리가 result[pos_y]로 접근할 수 있는 것은 result size 안에 있는 요소들만 접근할 수 있다. 책장에 책이 없는데, 3번째 칸에 있는 백설공주 책을 신데렐라 책으로 바꿔줘~라고 요청한다고 생각해보자. 얼마나 황당하겠는가. pos_y는 따라서 result의 size를 넘어가면 안된다.

 

그러면 왜 Play() 내부에서는 result값이 잘 출력됐을까? 특정 컴파일러나 디버그 모드에서는 잘 작동할 수 있지만, 운이 좋았던 것이고, 이는 명백히 잘못된 접근이다.

 

반환시 빈 벡터가 반환된 이유도 반환된 벡터의 size가 0이었기 때문이다.

 

 

최종 풀이😉

#include <iostream>
#include <vector>
#include <cstring> // memset()

using namespace std;

int n=0, m=0, answer=100;
int board[16][12];

vector<pair<int, int>> lines;
vector<pair<int, int>> lines_to_remove;
vector<int> origin_result;

// result의 값을 변환하거나 하지 않아서 참조로 넘기지 않아도 됨
// origin_result랑 같으면 true 다르면 false
bool Possible(vector<int> result){
    return origin_result==result;
}

void Make_Board(){
    //board초기화
    memset(board, 0, sizeof(board));

    // line을 그리기
    for(int i=0; i<(int)lines.size(); i++){
        board[lines[i].first][lines[i].second]=1;
        board[lines[i].first][lines[i].second+1]=2;
    }
    // lines_to_remove에 들어있는 선 지우기
    for(int i=0; i<(int)lines_to_remove.size(); i++){
        board[lines_to_remove[i].first][lines_to_remove[i].second]=0;  
        board[lines_to_remove[i].first][lines_to_remove[i].second+1]=0;  
    }

}

vector<int> Play(){
    //board 그리기
    Make_Board();

    vector<int> result(n); //n개의 공간 확보

    // player별로 이동시키기
    for(int player=0; player<n; player++){
        int pos_x =0, pos_y=player;

        while(pos_x<16){
            // 1이면 오른쪽 왼쪽 확인해서 1인 곳으로 이동하고 아래로 한 칸 내려가기
            // 0이면 가로줄이 없다는 뜻이므로 그냥 아래로 내려가기
            if(board[pos_x][pos_y]==1){
                //오른쪽 이동
                if(pos_y+1<n && board[pos_x][pos_y+1]==2){
                    pos_y++;
                }
            }
            else if(board[pos_x][pos_y]==2){
                // 왼쪽 이동
                if(pos_y-1>=0 && board[pos_x][pos_y-1]==1){
                    pos_y--;
                }
            }
            pos_x++;
        }
        result[pos_y]=player;
    }
    return result;
}

void FindMinLineSegments(int idx_line){
    // 종료 조건
    if(idx_line==m){
        vector<int> v = Play();
        // [갱신]처음과 결과가 같은데, 저장된 것보다 더 적은 선분을 이용했을 경우
        if(Possible(v)){
            //cout << "possible\n";
            //for(int i=0; i<m; i++){
            //    for(int j=0; j<n; j++){
            //        cout << board[i][j]<< " ";
            //    }
            //    cout << '\n';
            //}
            int num_of_line = m-(int)lines_to_remove.size();
            if (num_of_line<answer) answer = num_of_line;
        }
        return;
    }
    // 재귀 호출
    // m개의 선 중 lines[idx_line]을 지우는 경우
    lines_to_remove.push_back(lines[idx_line]);
    FindMinLineSegments(idx_line+1);

    // m개의 선 중 lines[idx_line]을 지우지 않는 경우
    lines_to_remove.pop_back();
    FindMinLineSegments(idx_line+1);
}

int main() {
    cin >> n >> m;
    
    for(int i=0;i<m;i++){
        int a, b;
        cin >> a >> b;
        // 문제는 배열이 1부터 시작하기 때문에 1을 뺀 값을 적용.
        a-=1;
        b-=1;
        lines.push_back({b, a});
    }

    origin_result = Play();
    FindMinLineSegments(0);
    cout << answer;
    return 0;
}

 

 이 게임에서는 가로줄끼리 서로 맞닿아 있는 경우가 없다고 가정해도 좋습니다.라고 문제에 나와 있었다.

기존 코드의 경우 1111인 경우오른쪽으로 가야하는지 왼쪽으로 가야하는지 모호했다. m개의 줄에 걸쳐 각 가로줄의 상태 (a, b)가 공백을 사이에 두고 주어진다.

따라서 a, a+1이 이어지게 되므로 둘 사이에서 이동만 가능하게 (a, b)는 1 (a+1, b)는 2라고 한 뒤 1이면 a+1 2면 a로 이동하도록  해주었다.