[백준] 어항 정리 23291번 (c++)

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

풀이 방법

 

구현 문제이다. 각 step에 따라서 함수를 나누고 구현을 했다.

 

먼저 문제를 풀이하기 전에 고려해야 할 자료구조를 생각해 보자

어항을 관리해야 한다. 

어항에서 step을 보면, 물고기를 한 칸 올린 후 90도 또는 180도를 돌리는 과정이 있다.

이를 구현하기 위해 2차원 배열을 선택했고, 90도, 180도 돌린 후 기존 어항 위에 올려놓아야 하므로 처음 시작을 y = n-1에서 시작했다.

 

각 step에 대해 살펴보자

 

step1

가장 작은 물고기의 인덱스를 찾아 +1을 해주면 된다.

void step1() { // 가장 작은 물고기 인덱스에 +1 해주는 함수
    int min_v = 987654321;
    vector<int> min_idx;
    for (int i = 0;i < n;i++) {
        if (arr[i] < min_v) {
            min_v = arr[i];
            min_idx.clear();
            min_idx.push_back(i);
        }
        else if (arr[i] == min_v) {
            min_idx.push_back(i);
        }
    }

    for (int i = 0;i < min_idx.size();i++) {        
        arr[min_idx[i]]++;
    }    
    return ;
}

 

step2

step2의 규칙을 살펴보면 새로 x 가로 행렬이 1x1, 2x1, 2x2, 3x2 이런 식으로 새로부터 한 칸 늘어난 후 가로 한 칸 규칙으로 늘어난다.

그리고 90도 돌린 후, 위에 올리게 된다면 시작 인덱스가 달라지게 된다.

그러므로 row만큼 매번 시작 인덱스를 이동시켜 준다. 

void step2() { // 90도 돌리기
    memset(temp, -1, sizeof(temp));
    for (int i = 0;i < n;i++) {
        temp[n-1][i] = arr[i];
    }
    col = 1, row = 1; // 새로, 가로
    start_idx = 0, remain_block = n;
    while(true) {
        // 종료 조건은 col <= 남은 길이
        if (col >= remain_block) break;

        // 스타트 인덱스 + row 부터 채워 나가면 된다.
        // x는 스타트 인덱스 + row - 1 부터 
        // y는 n-1부터  n-1 - col 까지
        for (int x = start_idx + row - 1; x >= start_idx; x--) {
            for (int y = n - 1; y > n -1 - col; y--) {
                // 연관 관계식 작성
                temp[n-2-(start_idx+row-1-x)][n-1-y+start_idx+row] = temp[y][x];
                temp[y][x] = -1;
            }
        }
        // 시작 인덱스 업데이트
        start_idx += row;
        // 남은 길이 업데이트 
        remain_block -= col;
        // row, col 업데이트
        if (col > row) {
            row++;
        }
        else col++;
        
    }

    return ;
}

step3

다음은 bfs를 수행한 후, 물고기수의 차이가 5이상 날 경우, cal 배열에 update를 할 물고기 수만큼 저장을 해두면 된다.

그 후 다시 bfs를 수행하며 계산했던 cal를 적용시켜 준다.

void step3() { // bfs해서 차이를 없애준다. 나누기 5만큼의
    // n-1, n-1에는 물고기가 무조건 있는 점이다. 여기부터 시작
    memset(visited, -1, sizeof(visited));
    memset(cal, 0, sizeof(cal));
    queue<pair<int, int> > q;
    q.push(make_pair(n-1, n-1)); // 무조건 존재하는 점
    visited[n-1][n-1] = 1;
    while(!q.empty()) {
        pair<int, int> now = q.front();
        q.pop();
        for (int i = 0;i < 4;i++) {
            int ny = now.first + dy[i];
            int nx = now.second + dx[i];
            if (ny < 0 || nx < 0 || ny > n-1 || nx >= 200) continue;
            if (temp[ny][nx] == -1) continue; // 비어있는 어항 패스하기
            if (visited[ny][nx] == -1) { // 방문한 적 없으면 추가해 주기
                q.push(make_pair(ny, nx));
                visited[ny][nx] = 1;
            }
            int diff = temp[now.first][now.second] - temp[ny][nx];  // 차이 구하기
            if ((abs(diff) / 5) >= 1) { // 차이 만큼 이동 시키기
                if (diff > 0) {
                    cal[now.first][now.second] -= (abs(diff) / 5);
                }
                else {
                    cal[now.first][now.second] += (abs(diff) / 5);
                }
            }
        }
    }
    
       // 위에서 실제로 계산한 것을 적용시켜 주는 부분이다.
    memset(visited, -1, sizeof(visited));    
    q.push(make_pair(n-1, n-1)); // 무조건 존재하는 지점
    visited[n-1][n-1] = 1; 
    while(!q.empty()) {
        pair<int, int> now = q.front();
        q.pop();
        if (cal[now.first][now.second] != 0) {
            temp[now.first][now.second] += cal[now.first][now.second];
        }
        for (int i = 0;i < 4;i++) {
            int ny = now.first + dy[i];
            int nx = now.second + dx[i];
            if (ny < 0 || nx < 0 || ny > n-1 || nx >= 200) continue;
            if (temp[ny][nx] == -1) continue;
            if (visited[ny][nx] == -1) {
                q.push(make_pair(ny, nx));
                visited[ny][nx] = 1;
            }            
        }
    }    
    return ;
}

step4

step2에서 돌린 어항을 다시 일자로 펴주는 함수이다.

두 단계로 나누어 펴주면 된다. (위에 올라간 부분), 그 영향을 받지 않은 부분

void step4() { // 돌린 배열을 펴는 함수
    int arr_idx = 0;
    for (int x = start_idx; x < start_idx + row; x++) {
        for (int y = n-1; y > n-1 - col; y--) {
            arr[arr_idx] = temp[y][x];
            arr_idx++;
        }
    }
    for (int i = start_idx+row;i <= n-1;i++) {
        arr[arr_idx] = temp[n-1][i];
        arr_idx++;
    }
}

step5

180도를 두 번 돌려준 후

step3를 진행하고, 다시 일자로 펴주는 함수이다.

void step5() { // 2번 180도 돌리는 함수
    memset(temp, -1, sizeof(temp));
    // temp 배열 다시 초기화
    for (int i = 0;i < n;i++) {
        temp[n-1][i] = arr[i];        
    }
    // 처음 올려 놓기
    int length = n / 2 ;
    for (int i = 0;i < length;i++) {
        temp[n-2][n-1-i] = temp[n-1][i];
        temp[n-1][i] = -1;
    }
    // 두번째로 올려 놓기
    int length2 = length / 2;
    
    for (int i = length + length2;i < n; i++) {
        temp[n-3][i] = temp[n-2][(length + length2) + (length + length2 - i) - 1];
        temp[n-2][(length + length2) + (length + length2 - i) - 1] = -1;
    }

    for (int i = length + length2;i < n; i++) {
        temp[n-4][i] = temp[n-1][(length + length2) + (length + length2 - i) - 1];
        temp[n-1][(length + length2) + (length + length2 - i) - 1] = -1;
    }
    step3(); // 물고기 수 조절 작업

    // 일자로 펴기
    for (int i = length + length2;i < n;i++) {
        for (int j = 0;j < 4;j++) {
            arr[(i - (length + length2)) * 4 + j] = temp[n-1-j][i];
        }
    }    
    return ;
}

check함수

어항의 물고기의 최대 값과 최소 값의 차이를 계산하고 해당 값이 k보다 작은지 검사하는 함수이다.

bool check() { // 최대 최소 차가 k이하인지 체크하기
    int min_v = 987654321, max_v = 0;
    for (int i = 0;i < n;i++) {
        if (min_v > arr[i]) {
            min_v = arr[i];
        }
        if (max_v < arr[i]) {
            max_v = arr[i];
        }
    }
    if (max_v - min_v <= k) return true;
    else return false;
}

 

main함수

위의 각 step을 1부터 5까지 돌아가며, check함수가 만족할 때까지 루프를 돌며 t를  업데이트해주면 된다.

int main() {
    cin >> n >> k;
    for (int i = 0;i < n;i++) {
        cin >> arr[i];
    }
    int t = 0;
    while(true) {
        if (check()) break;
        step1();
        step2();
        step3();
        step4();
        step5();
        t++;
    }
    cout << t << '\n';
    return 0;
}

이 문제에서 중요한 점은 90도 돌리기, 180도 돌리기와 같은 함수를 수행할 때, 배열의 인덱스를 조절하는 것이 핵심이다.