[코드트리] 금 채굴하기 C++

문제

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

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

 

생각한 방법

1. 탐색할 구역 map[i][j] 정하기
2. map[i][j]를 탐색할 다이아의 크기 k 정하기 for (k=0; k<n; k++)
3. 다이아몬드 만들기
4. 만들어진 구역에 금이 몇 개, 비용이 얼마인지
5. 손해 보지 않는다면 채굴할 수 있는 가장 많은 금의 개수와 비교해서 갱신

마름모 모양이란 특정 중심점을 기준으로 K번 이내로 상하좌우의 인접한 곳으로 이동하는 걸 반복했을 때 갈 수 있는 모든 영역이 색칠되어 있는 모양을 의미 -문제 내용-

재귀적으로 num==k가 될 때까지 num의 상하좌우를 표시하면 마름모 모양이 될 것 같다

 

 

풀이(시간초과)

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

using namespace std;

int n, m, answer;
int map[21][21];
bool exploreRange[21][21] = {false, };

// 좌(0, -1) 상(-1, 0) 우 (0, 1) 하(1, 0)
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};

// (exploreRange[i][j]==true && map[i][j]==1) gold++
int MiningGold(){
    int gold =0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(exploreRange[i][j] && map[i][j]==1) gold++;
        }
    }
    return gold;
}

// k크기의 다이아 만들기
void MakeRange(int i, int j, int size, int k){
    //if (size==0) exploreRange[i][j]=true;
    // 종료 조건
    if(size==k){
        return;
    }

    // 재귀 호출
    for(int dir=0; dir<4; dir++){
        exploreRange[i][j]=true;

        int nx= i+dx[dir];
        int ny= j+dy[dir];
        // 범위를 넘어가면 continue
        if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
        MakeRange(nx, ny, size+1, k);
    }
}


void PointToExplore(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            // 어차피 k=0부터 n-1까지 커지기 때문에 범위가 겹쳐도 상관 없음
            // map[i][j] 범위가 변경될 때 exploreRange를 초기화 해주면 된다
            memset(exploreRange, false, sizeof(exploreRange));

            // map[i][j]에서 k크기 다이아 만들기
            for(int k=1; k<=n; k++){
                MakeRange(i, j, 0, k);
                //cout << "(" << i << ", " << j <<") 구간에서 " <<k<<"크기의 다이아\n";
                //for(int x=0; x<n; x++){
                //    for(int y=0; y<n; y++){
                //        cout <<exploreRange[x][y] << " ";
                //    }
                //    cout << '\n';
                //}

                // 비용 계산 k=1이 문제에서의 k=0이기 때문에 k에 k-1을 대입해야 함
                int cost = k*k + (k-1)*(k-1);
                int gold = MiningGold();
                // 손해보지 않는다면 최대 금 갯수 갱신
                if(gold*m-cost>=0) answer = max(answer, gold);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> map[i][j];
        }
    }

    PointToExplore();
    cout << answer;

    return 0;
}

 

 

질문했더니 MakeRange 함수의 시간복잡도가 $O(3^k)$ 라고 한다. BFS의 원리를 이용하면 $O(n^2)$으로 줄일 수 있다고 한다...

 

 

시간복잡도 계산이 아직 좀 어려운 것 같다.

MakeRange 함수를 다시 보자!

// k크기의 다이아 만들기
void MakeRange(int i, int j, int size, int k){
    //if (size==0) exploreRange[i][j]=true;
    // 종료 조건
    if(size==k){
        return;
    }

    // 재귀 호출
    for(int dir=0; dir<4; dir++){
        exploreRange[i][j]=true;

        int nx= i+dx[dir];
        int ny= j+dy[dir];
        // 범위를 넘어가면 continue
        if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
        MakeRange(nx, ny, size+1, k);
    }
}

 

MakeRange 함수는 주어진 좌표로부터 4방향을 탐색(=각 호출마다 최대 4번 호출됨)하는 재귀함수이다. 

size=k라고 가정하면(어차피 MakeRange는 size==k일 때까지 스스로 호출하기 때문에 깊이가 k라는 것은 동일)

MakeRange(size)= 4*MakeRange(size+1) = 4*4*MakeRange(size-1) = ... = 4*4*4*4*...*MakeRange(0)

MakeRange(0)은 size==k라는 뜻이므로 return 한다 => O(1)

따라서 MakeRange()의 시간 복잡도는 4를 k번 곱한 $O(4^k)$가 된다.

 

풀이(Queue를 이용한 해결)

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring> // memset()

using namespace std;

int n, m, answer;
int map[21][21];
bool exploreRange[21][21] = {false, };

// 좌(0, -1) 상(-1, 0) 우 (0, 1) 하(1, 0)
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};

bool InRange(int x, int y){
    return x>=0 && x<n && y>=0 && y<n;
}
// (exploreRange[i][j]==true && map[i][j]==1) gold++
int MiningGold(){
    int gold =0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(exploreRange[i][j] && map[i][j]==1) gold++;
        }
    }
    return gold;
}

// k크기의 다이아 만들기
void MakeRange(int i, int j, int k){
    // 어차피 k=0부터 2*(n-1)까지 커지기 때문에 범위가 겹쳐도 상관 없음
    // map[i][j] 범위가 변경될 때 exploreRange를 초기화 해주면 된다
    memset(exploreRange, false, sizeof(exploreRange));
    queue<pair<int, int>> q;
    q.push({i, j});
    exploreRange[i][j]=true;

    for(int size=0; size<k; size++){
        int qSize = q.size();
        for(int qIdx =0; qIdx<qSize; qIdx++){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for(int dir=0; dir<4; dir++){
                int nx = x+dx[dir];
                int ny = y+dy[dir];
                if(!InRange(nx, ny) || exploreRange[nx][ny]) continue;
                exploreRange[nx][ny]=true;
                q.push({nx, ny});
            }
        }
    }
}


void PointToExplore(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            // map[i][j]에서 k크기 다이아 만들기
            for(int k=0; k<=2*(n-1); k++){
                //cout << "(" << i << ", " << j <<") 구간에서 " <<k<<"크기의 다이아\n";
                MakeRange(i, j, k);
                //for(int x=0; x<n; x++){
                //    for(int y=0; y<n; y++){
                //        cout <<exploreRange[x][y] << " ";
                //    }
                //    cout << '\n';
                //}

                int cost = k*k + (k+1)*(k+1);
                int gold = MiningGold();
                // 손해보지 않는다면 최대 금 갯수 갱신
                if(gold*m-cost>=0) answer = max(answer, gold);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> map[i][j];
        }
    }

    PointToExplore();
    cout << answer;

    return 0;
}

 

위 그림과 같은 방식으로 q에 있는 좌표를 저장하고 pop한 후, 해당 좌표의 상하좌우 좌표를 push하는 것을 k 크기만큼 반복하여 k크기의 다이아를 만든다.