백준 - 어항 정리 (23291번)

백준 - 어항 정리 (23291번)

와; 상당히 구현 문제였다. 시험장에서 만났으면 약간 뇌절와서 잘 못풀었을 것 같은 유형;

vector, queue, deque 섞어가면서 필요한 곳마다 사용했고, 전체 map은 그냥 2차원 배열로 관리했다.
덕분에 시간은 0ms 걸린 것 같다.
인덱스 잘 신경쓰면서 주어진 요구사항 그대로 구현하면 된다.
난 안했지만 요구사항이 좀 많아서 각 단계마다 함수화하는게 코드 짜는데에는 조금이라도 도움이 될 것 같다. (난 그냥 코드 그대로 복붙했다)

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

using namespace std;

int n, k;
int fish_map[101][101];
int row_size[101];
int row_start = 100;
int row_end = 101;
int col_start = 0;
void Print_Map(const char *s)
{
	printf("[%s] [%d ~ ]\n", s, col_start);
	for (int i = row_start; i < row_end; i++) {
		printf("[%d] Row[%d] \t: ", row_size[i], i);
		for (int j = col_start; j < row_size[i]; j++)
			printf("%d ", fish_map[i][j]);
		printf("\n");
	}
}
void Print_Row_Size()
{
	printf("Print Row Size\n");
	for(int i = 0; i < 101; i++) {
		if (row_size[i] != 0)
			printf("[%d] : %d\n", i, row_size[i]);
	}
}
int rowDir[4] = { -1, 0, 1, 0 };
int colDir[4] = { 0, 1, 0, -1 };
int main(void)
{
	cin >> n >> k;
	row_size[row_start] = n;
	for (int i = 0; i < n; i++) 
		cin >> fish_map[row_start][i];

	//Print_Map("Initial Print Map");
	int min_fish_num = 1000001;
	int max_fish_num = -1;
	int iter = 0;
	while (1) {
		// 가장 바닥에서 수가 적은 어항의 물고기 개수를 찾음
		for (int i = 0; i < row_size[row_start]; i++) {
			max_fish_num = max(fish_map[row_start][i], max_fish_num);
			min_fish_num = min(fish_map[row_start][i], min_fish_num);
		}

		// 만약 그 차이가 k 이하면 break
		if (max_fish_num - min_fish_num <= k)
			break;

		// 가장 물고기 개수가 적은 어항에 물고기를 1개 추가
		for (int i = 0; i < row_size[row_start]; i++) {
			if (fish_map[row_start][i] == min_fish_num)
				fish_map[row_start][i]++;
		}

		// 직사각형 벡터를 만들고, 쌓기를 반복
		int nrow = 1, ncol = 1;
		int nrow_start;
		int grow, gcol;
		while (1) {
			int bcol = ncol;
			if (nrow == ncol) {
				nrow++;
				nrow_start = row_start - 1;
			} 
			else {
				ncol = nrow;
				nrow_start = row_start;
			}
			if (nrow * ncol > n)
				break;

			deque<int> q;
			for (int i = col_start; i < col_start + bcol; i++) 
				for (int j = row_start; j < row_end; j++) 
					q.push_back(fish_map[j][i]);
				
			
			row_start = nrow_start;
			col_start += bcol;
			for(int i = row_end-2; i >= row_start; i--) {
				row_size[i] = col_start + ncol;
				for (int j = col_start; j < col_start + ncol; j++) {
					int num = q.back();  q.pop_back();
					fish_map[i][j] = num;
				}
			}
			grow = nrow;
			gcol = ncol;
		}

		// 주변과 교환을 함
		int diff_map[101][101];
		for (int i = 0; i < 101; i++) 
			for (int j = 0; j < 101; j++) 
				diff_map[i][j] = 0;

		for (int i = row_start; i < row_end; i++) {
			for (int j = col_start; j < row_size[i]; j++) {
				for (int k = 0; k < 4; k++) {
					int nrow = i + rowDir[k];
					int ncol = j + colDir[k];
					if (nrow < row_start || nrow > row_end - 1)
						continue;
					if (ncol < col_start || ncol > row_size[i] - 1)
						continue;
					if (ncol > row_size[nrow] - 1)
						continue;
					if (fish_map[i][j] <= fish_map[nrow][ncol])
						continue;
					int diff = 0;
					diff = (int)(fish_map[i][j] - fish_map[nrow][ncol]) / 5;
					diff_map[i][j] -= diff;
					diff_map[nrow][ncol] += diff;
				}
			}
		}
		for (int i = row_start; i < row_end; i++) 
			for (int j = col_start; j < row_size[i]; j++) 
				fish_map[i][j] += diff_map[i][j];

		// 다시 1층에다 쌓음
		vector<int> v;
		for (int i = col_start; i < col_start + gcol; i++) 
			for (int j = row_end - 1; j >= row_start; j--)
				v.push_back(fish_map[j][i]);
			
		for (int i = col_start + gcol; i < row_size[row_end - 1]; i++) 
			v.push_back(fish_map[row_end - 1][i]);
		
		for (int i = 0; i < v.size(); i++) 			
			fish_map[row_end - 1][i] = v[i];

		for (int i = row_start; i < row_end; i++) 
			row_size[i] = 0;
		row_size[row_end - 1] = n;
		row_start = 100;
		row_end = 101;
		col_start = 0;

		// 절반 시계방향으로 180도 돌려서 읽고, 쌓고 이 과정 2회 반복
		int size = v.size();
		for (int j = 0; j < size/2; j++) 
			fish_map[row_start - 1][size/2 + j] = v[size/2 - j - 1];
		row_start = 99;
		row_size[row_start] = n;
		row_end = 101;
		col_start = size / 2;
		
		queue<int> v1;
		for (int i = row_end - 1; i >= row_start; i--) 
			for(int j = col_start + col_start/2 - 1; j >= col_start; j--) 
				v1.push(fish_map[i][j]);
		
		for (int i = row_start - 2; i < row_start; i++) {
			for (int j = col_start + col_start/2; j < n; j++) {
				int num = v1.front(); v1.pop();
				fish_map[i][j] = num;
			}
			row_size[i] = n;
		}
		row_start = 97;
		col_start = col_start + col_start / 2;
		
		// 주변과 열교환
		int diff_map2[101][101];
		for (int i = 0; i < 101; i++)
			for (int j = 0; j < 101; j++)
				diff_map2[i][j] = 0;

		for (int i = row_start; i < row_end; i++) {
			for (int j = col_start; j < row_size[i]; j++) {
				for (int k = 0; k < 4; k++) {
					int nrow = i + rowDir[k];
					int ncol = j + colDir[k];
					if (nrow < row_start || nrow > row_end - 1)
						continue;
					if (ncol < col_start || ncol > row_size[i] - 1)
						continue;
					if (ncol > row_size[nrow] - 1)
						continue;
					if (fish_map[i][j] <= fish_map[nrow][ncol])
						continue;
					int diff = 0;
					diff = (int)(fish_map[i][j] - fish_map[nrow][ncol]) / 5;
					diff_map2[i][j] -= diff;
					diff_map2[nrow][ncol] += diff;
				}
			}
		}
		for (int i = row_start; i < row_end; i++)
			for (int j = col_start; j < row_size[i]; j++)
				fish_map[i][j] += diff_map2[i][j];

		// 다음 단계에서 쓸 1차원 배열 다시 만들기
		queue<int> q3;
		for (int i = col_start; i < n; i++) 
			for (int j = row_end - 1; j >= row_start; j--) 
				q3.push(fish_map[j][i]);
		
		int q3size = q3.size();
		for (int i = 0; i < q3size; i++) {
			int num = q3.front(); q3.pop();
			fish_map[row_end - 1][i] = num;
		}
		for (int i = row_start; i < row_end; i++)
			row_size[i] = 0;
		row_size[row_end - 1] = n;
		row_start = 100;
		row_end = 101;
		col_start = 0;

		min_fish_num = 1000001;
		max_fish_num = -1;
		iter++;
	}

	cout << iter << "\n";

	return 0;
}