[코드트리 챌린지] 금 채굴하기

[문제]

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

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

 

[문제 풀이]

n * n 배열에서 금을 얻을때마다 m씩 얻고 마름모의 채굴비용은 K∗K+(K+1)∗(K+1) 로 소비될때 채굴비용이 음수가 되지 않는 내에서 최대 금을 몇개 얻을 수 있는지 요구하는 문제이다.

 

위의 그림의 마름모는 K가 1일때고 2일때는 아래와 같은 모습이다.

 

사실 잘 생각해보면 어딘가에서 유독 많이 본 모습이라고 느낄만한데 바로 BFS 알고리즘을 돌릴때 위의 그림들과 같이 커지는 모습을 눈치챌 수 있다.

 

그러면 해당 문제는 이제 0,0부터 n - 1, n - 1까지 돌리면서 해당 위치에서 bfs의 넓이가 0일때부터 bfs의 넓이가 n일때까지 돌려주는 것을 요구하는 문제로 바뀐다.

추가로 bfs를 n번까지만 하면 되는 이유는 0,0의 위치에서 볼때 n까지 돌리면 우측 하단에 공간이 남을 수 있지만 가운데 좌표에서 n일때까지 돌리면 모든 공간을 채울 수 있으므로 굳이 0,0에서 모든 공간을 채울 필요가 없기 때문이다.

[회고]

bfs를 n번 돌리는 부분에서 처음에 실수를 했다. 두번째에는 이를 해결하기 위해서 내부에 cur 변수를 추가로 뒀지만 조금 더 다른 방법이 없나 확인을 해보자.

[코드]

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int boards[51][51];
int visited[51][51];

bool inRange(int x, int y){
    if(x >= 0 && x < n && y >= 0 && y < n){
        return true;
    }
    return false;
}

void visitedClear(){
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            visited[i][j] = 0;
        }
    }
    return;
}

int four(int n){
    int answer = 1;
    for(int i = 0;i<n;i++){
        answer *= 4;
    }
    return answer + 1;
}

int bfs(int r, int c, int n){
    int answer = 0;
    visitedClear();

    queue<pair<pair<int,int>,int > > q;
    q.push(make_pair(make_pair(r,c),0) );
    if(boards[r][c] == 1){
        answer += m;
    }
    visited[r][c] = 1;


    while(q.size() > 0){
        int curX = q.front().first.first;
        int curY = q.front().first.second;
        int cur = q.front().second;
        if(cur == n){
            break;
        }
        q.pop();
        for(int i = 0;i<4;i++){
            int nextX = curX + dx[i];
            int nextY = curY + dy[i];
            if(inRange(nextX,nextY) == true && visited[nextX][nextY] == 0){
                //만일 코인이라면.
                if(boards[nextX][nextY] == 1){
                    // cout<<"next : "<<nextX<<" "<<nextY<<" ";
                    answer += m;
                }
                visited[nextX][nextY] = 1;
                q.push(make_pair(make_pair(nextX,nextY),cur + 1 ) );
            }
        }
    }
    return answer;
}

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

    //1. 모두 돌기.
    //2. 마름모 키우기 => bfs n번 범위.
    // cout<<"마름모 돌리기 : "<<endl;
    int answer = 0;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            for(int k = 0;k<n;k++){
                int temp = bfs(i,j,k);
                // cout<<"i : "<<i<<" j : "<<j<<" k : "<<k<<" ";
                // cout<<temp<<endl;
                if( temp - ((k * k) + ( k + 1) * (k + 1)) >= 0 ){
                    answer = max(answer, temp / m);
                }
                // cout<<temp<<" ";
            }
            // cout<<endl;
        }
        // cout<<endl;
    }
    cout<<answer<<endl;
    return 0;
}