[백준 23291][C++] 어항 정리

문제

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

23291번: 어항 정리

 

풀이 과정

해당 문제는 풀이에 실패했다. 따라서 해당 문제에 대한 다른 사람들의 코드를 둘러보게 되었다. 그중 정말 깔끔하고 잘 구현되었다고 생각되는 포스팅의 코드를 살펴보는 식으로 글을 진행할 것이다.

 

https://kimjingo.tistory.com/111

[백준 23291번] 어항 정리(C++ 풀이)

고민하다 풀이에 실패하고 해당 풀이를 보았는데 눈이 떠진 느낌이었다. 검색한 풀이들 중 가장 과정이 명료했고 배울 점이 많았다. 코드뿐만 아니라 풀이도 자세하고 이해하는데 많은 도움이 되었다.

 

1. if_end 함수를 이용한 종료 조건 처리

비교적 간단한 부분이라 직접 while문에서 처리할 수 있지만, 따로 bool 함수로 구현하여 코드의 가독성을 높였습니다.

max_element와 min_element를 이용한 최대 최소 값 구하는 방식을 알고 놀랐다. 혼자 알고리즘 공부를 하며 작성한 사람들의 코드를 보면서 C++을 공부했던 터라 이런 자세한 기능들에 대해서 알게 되어서 또 배울 점이 있는 코드였다. 여러 코드와 포스팅을 검색해서 봤을 때 해당 함수를 이용하는 코드를 거의 못 봤던 것 같은데 이런 라이브러리들에 대한 공부도 필요하다는 것을 느꼈다.

 

2. 어항을 정리하는 (말았다가 펴는 동작) 함수 구현

나는 따라서 배열에 직접 계속 값을 업데이트하는 것 대신 한 벡터 안에 각 좌표들을 입력하여 변경하여 처리하는 방식을 선택했었다.(구현엔 실패했지만...) 구현에서 제일 애를 먹었던 부분이 해당 함수이다.

 

3. 2차원 vector의 구현과 초기화

분명 벡터라는 자료구조를 매우 자주 쓰고 있음에도 해당 코드를 보면서 많이 다르다는 느낌을 받았다. 새로운 벡터를 선언하고 할당하며 초기화하는 과정들에서  그 이점들이 확 느껴졌다.

 

 

소스 코드

/* 
 * 참고 소스
 * https://kimjingo.tistory.com/111
 */

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

using namespace std;

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

vector<vector<int>> board;

bool if_end(){
    int max_fishes = *max_element(board[0].begin(), board[0].end());
    int min_fishes = *min_element(board[0].begin(), board[0].end());
    return ((max_fishes - min_fishes) <= K);
}

void move_fishes(){
    vector<vector<int>> new_board = board;

    for(int y=0; y<N; ++y){
        for(int x=0; x<N; ++x){
            if(board[y][x] == -1) continue;
            for(int d=0; d<4; ++d){
                int ny=y+dy[d];
                int nx=x+dx[d];
                if(ny<0 || nx<0 || ny>=N || nx>=N || board[ny][nx]== -1) continue;
                //새로운 값을 new_board 에 기록했으므로 중복 없이 모든 칸에 발생한 상황 반영
                new_board[y][x] += (int) (board[ny][nx]-board[y][x]) / 5;
            }
        }
    }

    vector<int> flat_bowl;
    for(int x=0; x<N; ++x){
        for(int y=0; y<N; ++y){
            if(new_board[y][x] == -1) continue;
            else flat_bowl.push_back(new_board[y][x]);
        }
    }

    //board를 초기화 한 후 board[0]를 flat_bowl로 교체
    board = vector<vector<int>>(N, vector<int>(N, -1));
    board[0] = flat_bowl;
}

void move(){
    int ly=1, lx=1; //length y, length x
    int sx=0; //start x
    //1. 물고기 추가
    int min_fishes = *min_element(board[0].begin(), board[0].end());
    for(int i=0; i<N; ++i){
        if(board[0][i] == min_fishes) board[0][i]++;
    }
    //2. 어항을 말며 이동
    while(sx + ly + lx <= N){
        for(int y=0; y<ly; ++y){
            for(int x=0; x<lx; ++x){
                int ny = lx - x;
                int nx = sx + lx + y;
                board[ny][nx] = board[y][x + sx];
                board[y][x + sx] = -1;
            }
        }
        sx += lx;
        if(ly == lx) ly++;
        else lx++;

    }

    //3. 물고기 이동
    move_fishes();

    //4. 중심을 기준으로 어항 2번 이동
    sx = 0;
    ly = 1;
    lx = N/2;

    for(int i=0; i<2; ++i){
        for(int y=0; y<ly; ++y){
            for(int x=0; x<lx; ++x){
                int ny = 2 * ly - y - 1;
                int nx = 2 * lx + sx - x - 1;
                board[ny][nx] = board[y][x + sx];
                board[y][x + sx] = -1;
            }
        }

        sx += lx;
        lx /= 2;
        ly *= 2;
    }

    //5. 물고기 이동
    move_fishes();

}

int solve(){
    int count = 0;
    while(!if_end()){
        count++;
        move();
    }

    return count;
}

int main(){
    cin >> N >> K;
    board = vector<vector<int>>(N, vector<int>(N, -1));
    for(int i=0;i<N;++i){
        cin >> board[0][i];
    }
    cout << solve();
    return 0;
}

 

결과 및 후기

내가 이전의 코드와 현재의 코드를 비교하면서 볼 때는 나름 발전한 것 같은 느낌이 드는데 다른 사람의 깔끔한 풀이를 볼 때면 항상 부족함이 느껴진다. C++ 라이브러리들에 대한 공부와 자주 쓸 수 있는 유용한 함수들에 대한 공부를 해야겠다. 그리고 해당 문제를 풀이한 포스팅과 다른 여러 풀이에 따르면 배열 회전 문제는 굉장히 유명한 문제인 것 같은데 나는 구현이 힘들었다. 알고리즘 공부가 더 필요하다.