[백준/BOJ] 백준 23291번 : 어항 정리

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

23291번: 어항 정리

 

어항을 상태 2차원 배열에 bowl에 표시하였고, 각 열에 대한 높이를 height에 저장해 놓았다. 물고기 수가 가장 적은 어항에 물고기를 한마리 넣기, 어항을 쌓기, 물고기의 수 조절하기, 어항을 바닥에 일렬로 놓기, 가운데 중심으로 어항 쌓기를 함수로 분리하여 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
using namespace std;

int n, k;
int height[105]; //[열 위치] = 해당 열 위치에 존재하는 어항의 개수(높이)
int bowl[105][105]; //[어항의 행 위치][어항의 열 위치]
int result = 0;
int start = 0;
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

// 물고기 수가 가장 적은 어항에 물고기를 한마리 넣는다
void min_finsh() {

	vector<int> min_index;
	int min_value = 987654321;

	for (int j = 0; j < n; j++) {
		if (bowl[100][j] < min_value) { //더 작은 값을 찾았을때
			min_index.clear();
			min_index.push_back(j);
			min_value = bowl[100][j];
		}
		else if (bowl[100][j] == min_value) {
			min_index.push_back(j);
		}
	}

	//물고기 수가 가장 적은 어항에 물고기를 한마리씩 넣는다.
	for (int i = 0; i < min_index.size(); i++) {
		bowl[100][min_index[i]]++;
	}
}

// 공중부양해서 시계 방향으로 90도 회전
// 할 수 없으면 false 반환
bool trun_left(int range_left, int range_right, int range_height) {

	// 범위를 넘어가서 회전할 수 없는지 확인
	if (range_right + range_height >= n) {
		return false;
	}

	// 공중부양해서 시계 방향으로 90도 회전
	for (int i = 100; i > 100 - range_height; i--) {
		for (int j = range_left; j <= range_right; j++) {
			int here_row = i;
			int here_col = j;

			int there_row = 100 - 1 - (range_right - here_col);
			int there_col = range_right + 1 + (100 - here_row);
			bowl[there_row][there_col] = bowl[here_row][here_col];
			bowl[here_row][here_col] = 0;
			height[here_col]--;
			height[there_col]++;
		}
	}

	start++;

	return true;
}

// 어항을 쌓는다
void bowl_up() {

	// 가장 왼쪽 어항을 오른쪽 위에 올려 놓는다
	bowl[100 - 1][start + 1] = bowl[100][start];
	bowl[100][start] = 0;
	height[start]--;
	height[start + 1]++;

	start++;


	// 2개 이상 쌓여있는 어항을 모두 공중 부양 시킨 다음 
	// 시계 방향으로 90도 회전 시킨다.
	while (1) {
		//2개 이상 쌓여 있는 어항의 범위를 구한다
		int range_left = start;
		int range_right = range_left;

		for (int i = range_left; i < n; i++) {
			if (height[i] >= 2) { //2개 이상 쌓여 있을때
				range_right = i;
			}
			else {
				break;
			}
		}

		//range_left 부터 range_right 를 공중 부양해서, 시계 방향으로 90도 회전
		if (trun_left(range_left, range_right, height[range_left]) == false) {
			break;
		}

	}

}

// 물고기의 수를 조절한다
void finsh_control() {
	vector<vector<int>> plus_bowl(105, vector<int>(105, 0));
	vector<vector<int>> minus_bowl(105, vector<int>(105, 0));
	set<vector<pair<int, int>>> check;

	for (int i = 0; i < 105; i++) {
		for (int j = 0; j < 105; j++) {

			if (bowl[i][j] == 0) {
				continue;
			}

			pair<int, int> here = make_pair(i, j);

			for (int dir = 0; dir < 4; dir++) {
				pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);

				vector<pair<int, int>> this_check;

				this_check.push_back(here);
				this_check.push_back(there);
				sort(this_check.begin(), this_check.end());

				// 이미 확인한적 있는 짝일때
				if (check.count(this_check) != 0) {
					continue;
				}
				check.insert(this_check);

				if (there.first < 0 || there.first >= 105 || there.second < 0 || there.second >= 105 || bowl[there.first][there.second] == 0) {
					continue;
				}

				int diff = abs(bowl[here.first][here.second] - bowl[there.first][there.second]);
				int d = diff / 5;

				if (d > 0) {

					// 많은 곳에 있는 물고기를 적은곳으로 d 만큼 보낸다
					if (bowl[here.first][here.second] > bowl[there.first][there.second]) {
						plus_bowl[there.first][there.second] += d;
						minus_bowl[here.first][here.second] += d;
					}

					else if (bowl[here.first][here.second] < bowl[there.first][there.second]) {
						plus_bowl[here.first][here.second] += d;
						minus_bowl[there.first][there.second] += d;
					}

				}

			}

		}
	}

	for (int i = 0; i < 105; i++) {
		for (int j = 0; j < 105; j++) {
			bowl[i][j] += plus_bowl[i][j];
			bowl[i][j] -= minus_bowl[i][j];
		}
	}
}

// 다시 어항을 바닥에 일렬로 놓기
void bowl_down() {
	vector<vector<int>> next_bowl(105, vector<int>(105, 0));

	int check_index = 0;

	for (int j = start; j < n; j++) {
		for (int i = 100; i > 100 - height[j]; i--) {
			next_bowl[100][check_index] = bowl[i][j];
			check_index++;
		}
	}

	for (int i = 0; i < 105; i++) {
		for (int j = 0; j < 105; j++) {
			bowl[i][j] = next_bowl[i][j];
		}
	}

	// 높이 표시 초기화
	for (int i = 0; i < n; i++) {
		height[i] = 1;
	}

	start = 0;
}

// 가운데 중심으로 왼쪽 n/2개를 공중 부양시켜 전체를 시계 방향으로 180도 회전 시킨 다음, 오른쪽 n/2개의 위에 놓기 2번 반복
void trun_min() {

	int range_left = start;
	int range_right = n - 1;
	int mid = (range_right - range_left) / 2;

	// 1번째
	for (int i = range_left; i <= mid; i++) {
		int here_row = 100;
		int here_col = i;

		int there_row = here_row - 1;
		int there_col = range_right - here_col;

		bowl[there_row][there_col] = bowl[here_row][here_col];
		bowl[here_row][here_col] = 0;
		height[here_col]--;
		height[there_col]++;
	}

	start = mid + 1;
	range_left = mid + 1;
	mid = range_left + (range_right - range_left) / 2;

	// 2번째
	for (int j = range_left; j <= mid; j++) {
		int before_height_j = height[j];
		for (int i = 100; i > (100 - before_height_j); i--) {
			int here_row = i;
			int here_col = j;

			int there_row;

			if (i == 100) {
				there_row = 97;
			}
			else {
				there_row = 98;
			}

			int there_col = mid + 1 + mid - here_col;

			bowl[there_row][there_col] = bowl[here_row][here_col];
			bowl[here_row][here_col] = 0;
			height[here_col]--;
			height[there_col]++;
		}
	}
	start = mid + 1;

}

// 가장 많이 들어있는 어항과 가장 적게 들어있는 어항 차이 구하기
int check_diff() {

	int max_value = -1;
	int min_value = 987654321;

	//가장 많이 들어 있는 어항과 가장 적게 들어있는 어항의 물고기 차이 구하기
	for (int j = 0; j < 105; j++) {

		if (bowl[100][j] == 0) {
			continue;
		}

		min_value = min(min_value, bowl[100][j]);
		max_value = max(max_value, bowl[100][j]);
	}

	return max_value - min_value;
}

int main() {

	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;

		bowl[100][i] = input; //행 위치 100을 가장 아래 위치라고 생각
		height[i]++;
	}

	while (1) {

		int diff = check_diff();
		if (diff <= k) {
			break;
		}

		result++;

		// 물고기 수가 가장 적은 어항에 물고기를 한마리 넣기
		min_finsh();

		// 어항을 쌓기
		bowl_up();

		// 물고기의 수를 조절
		finsh_control();

		// 다시 어항을 바닥에 일렬로 놓기
		bowl_down();

		// 가운데 중심으로 어항 쌓기
		trun_min();

		// 물고기의 수를 조절
		finsh_control();

		// 다시 어항을 바닥에 일렬로 놓기
		bowl_down();

	}

	cout << result << "\n";

	return 0;
}