[백준] 23291번: 어항 정리

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

23291번: 어항 정리

어항 정리라고 해서 상어로부터 벗어났다고 생각하셨나요? 이번 문제는 마법사 상어가 어항 정리를 하는 내용입니다 ㅎㅎ

소요 시간

골드 2 기준으로 2시간 20분이 걸렸습니다.
그리고 노래 부르면서 풀었습니다. 그러면 안되는데 그죠? 요새 좀 빠져가지고.. 태도가 불량합니다.

아 그리고 이것은 자랑인데요, 대략 모노미노도미노2 부터는 쭉 제출 한 번 만에 맞았습니다! 를 받고 있어요. PS 공부를 시작하기 전에는 한번에 맞았습니다! 가 뜨는 경우가 잘 없었습니다. 애초에 습관이 여러 번 제출을 해 보면서 코드를 수정하는 것으로 잡혀 있었어서 그런 것도 있습니다. 하지만 대부분의 코딩 테스트에서는 전체 테스트케이스가 공개되어 있지 않잖아요? 그러니까 코딩테스트에서는 주어진 작은 테스트케이스와 본인이 만든 테스트 케이스로만 코드를 점검한 뒤 한번에 맞았습니다! 를 노려야 하는 겁니다. 그래서 코딩테스트를 대비중인 최근에는 제출을 최대한 미루고, 시간복잡도를 계산하고 여러 코너 케이스를 대입하면서 한번에 맞았습니다! 를 받을 수 있게 하는 데에 정성을 쏟았습니다. 그랬더니 요즘에는 제출 한번에 맞았습니다! 가 뜨는 경우가 압도적으로 많아졌네요. 실력이 는 것 같아서 행복합니당~!

다른 유저들의 평가

배열을 공중부양&회전 과정을 통해 돌돌 마는 것을 구현하기 위해 생각이 많이 필요하다, 실수하기 쉽고 까다롭다는 평가가 있었습니다.
저도 시간이 꽤 걸렸구요, 사실 구현 문제 치고 구현할 것이 아주 많은 편은 아니지만 배열을 돌돌 마는 것이 실수하기 쉬워서 어려웠던 것 같습니다. 이걸 실제 시험장에서 풀었다면 3시간 이상이 걸리지 않았을까 하는... 그래도 머리를 막~~~짜서 배열을 돌돌 마는 부분만 잘 해내면 잘 할 수 있습니다!

구상

1. 가장 작은 수의 물고기가 있는 어항에 물고기를 한마리 넣는 함수
2. 첫번째 공중부양&회전&물고기조절&다시펴기 함수
3. 두번째 공중부양&회전&물고기조절&다시펴기 함수
이렇게 적어두니 별 거 없어 보이지만 어려웠습니다...

포인트 - 어떻게 배열을 돌돌 말 것인가?

저의 경우에는 vector<vector<int>> 로 어항들을 저장했습니다.
그리고 바닥면에서 2개 이상 쌓인 어항들을 공중부양시켜야 하기 때문에, 바닥면이 왼쪽에 있다고 생각하고 풀었습니다. 즉,

이런 느낌인데 이해가 가셨으면 좋겠네요. 두 함수 다 이렇게 비슷하게 구현합니다.

+) 팁

주어진 테스트 케이스는 어항이 8개와 4개인 경우밖에 없습니다. 16개인 경우, 24개인 경우 등을 만들어서 테스트 해 보면 좋을 듯 합니다! 굳이 모든 로직을 테스트 해 볼 필요는 없고 돌돌 마는 그 구현만이라도 제대로 됐는지 확인해 보시길 권장합니다!

코드

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};

void flat(vector<vector<int> >& fishes, int N, int start_pos) {
    vector<vector<int> > prev(fishes);
    int index = 0;
    for(int i=start_pos; i<N; i++) {
        for(int j=0; j<prev[i].size(); j++) {
            fishes[index][0] = prev[i][j];
            fishes[index].resize(1);
            index++;
        }
    }
}

void adjust_fishes(vector<vector<int> >& fishes, int N, int start_pos) {
    vector<vector<int> > add(N, vector<int>(N, 0));
    for(int i=start_pos; i<N; i++) {
        for(int j=0; j<fishes[i].size(); j++) {
            for(int k=0; k<4; k++) {
                int nx = i + dx[k]; int ny = j + dy[k];
                if(nx < start_pos || nx > N-1 || ny > fishes[nx].size()-1 || ny < 0) continue;
                int d = (fishes[i][j] - fishes[nx][ny])/5;
                if(d > 0) {
                    add[i][j] -= d;
                    add[nx][ny] += d;
                }
            }
        }
    }
    for(int i=start_pos; i<N; i++) {
        for(int j=0; j<fishes[i].size(); j++) {
            fishes[i][j] += add[i][j];
        }
    } 
}

void up_rotate(vector<vector<int> >& fishes, int N) {
    int start_pos = 1;
    fishes[1].push_back(fishes[0][0]);
    while(true) {
        int next_pos = N-1;
        int height = fishes[start_pos].size();
        int width = 0;
        for(int i=start_pos; i<N; i++) {
            if(fishes[i].size() < 2) {
                next_pos = i;
                break;
            }
            width += 1;
        }
        if(next_pos + height > N) break;

        vector<vector<int> > up_fishes(fishes.begin() + start_pos, fishes.begin() + next_pos);
        for(int i=width-1; i>=0; i--) {
            for(int j=height-1; j>=0; j--) {
                fishes[j+next_pos].push_back(up_fishes[i][j]);
            }
            fishes[i+start_pos].resize(1);
        }
        start_pos = next_pos;
    }
    adjust_fishes(fishes, N, start_pos);
    flat(fishes, N, start_pos);
}

void half_rotate(vector<vector<int> >& fishes, int N) {

    for(int half = N/2; half<N; half++) {
        fishes[half].push_back(fishes[N-half-1][0]);
    }
    for(int i=fishes[N/2].size()-1; i>=0; i--) {
        for(int j=N/2+N/4-1; j>=N/2; j--) {
            fishes[N/2+(N-j)-1].push_back(fishes[j][i]);
        }
    }
    adjust_fishes(fishes, N, N/2+N/4);
    flat(fishes, N, N/2+N/4);
}

void add_fish(vector<vector<int> >& fishes, int N) {
    int min_fish = INT_MAX;
    for(int i=0; i<N; i++) {
        min_fish = min(min_fish, fishes[i][0]);
    }
    for(int i=0; i<N; i++) {
        if(min_fish == fishes[i][0]) {
            fishes[i][0] += 1;
        }
    }
}

int main(int argc, char** argv)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int N, K;
    int min_fish = INT_MAX; int max_fish = -1;
    cin >> N >> K;
    vector<vector<int> > fishes(N, vector<int>(1, 0));
    for(int i=0; i<N; i++) {
        cin >> fishes[i][0];
        min_fish = min(fishes[i][0], min_fish);
        max_fish = max(fishes[i][0], max_fish);
    }

    int cnt = 0;
    while(max_fish - min_fish > K) {
        cnt ++;
        add_fish(fishes, N);
        up_rotate(fishes, N);
        half_rotate(fishes, N);
        min_fish = INT_MAX; max_fish = -1;
        for(int i=0; i<N; i++) {
            min_fish = min(fishes[i][0], min_fish);
            max_fish = max(fishes[i][0], max_fish);
        }
    }
    cout << cnt << endl;
    return 0;
}

오류는 댓글로 알려주세용~