BOJ 23291. 어항 정리
1. 문제설명
- 지시된 사항대로 시뮬레이션을 구현하면 된다.
-
뭐 하나라고 딱 말하기가 애매해서, 예제 하나로 구현의 과정을 보겠다.
- 입력값
- 8은 배열 요소의 개수
- 시뮬레이션을 몇 번을 거치면 원소의 최대-최소가 7보다 작아지는가?
8 7 5 2 3 14 9 2 11 8 - 과정 1 : 어항의 최소값을 찾아 +1, 여러 개라면 전부 +1
5 3 3 14 9 3 11 8
- 과정 2 : 어항의 가장 왼쪽 값을 어항의 위에 올리기 (문제 속 그림 3)
- 과정 3 : 규칙에 따라 더 이상 회전하지 못할 때까지 회전
- 여기부터는 문제 속 그림과 상하 반전이 되어 있습니다. 참고해주세요.
9 3 11 8 14 5 3 3 - 과정 4: 일렬로 만들기, 어항의 가장 아래부터 위에까지 순서대로
9 10 5 5 6 3 10 8(문제 속 그림 8)
-
과정 5 : 가운데를 중심으로 N/2개를 시계 방향으로 180도 회전 후 오른쪽 N/2개의 위에 놓기 (2회 반복)
(문제 속 그림 11) 10 8 10 9 5 5 3 6 - 과정 6 : 일렬로 만들기 (참고로 4번과 만드는 과정이 다름.)
10 9 6 3 8 9 5 6(그림 12)
- 문제 분류
- Implementation, Sorting, Simulation
2. 알고리즘 설계
- 문제를 보면 평탄화와 행렬화가 지속된다.
- 그래서 두 가지 변수를 사용하였다.
- 평탄화 배열, 행렬화 배열
vector<int> v,vector<deque<int>> dq
- 이 문제는 deque로 풀면 꽤나 수월하다.
- 그 이유는 행렬을 회전하는 곳에서 나옴.
- 과정 1 : 평탄화 배열에서 최소값을 찾아주면 된다.
- 간단하니 코드 생략
- 과정 2 : 회전
- deque를 벡터로 선언해둔 상태라 초기에는 아무것도 없다.
- 그래서 방을 하나 만들어준다.
- 이게 첫번째 층을 의미한다.
- 즉, 문제 속 그림 2번의 상태이다.
dq(위에서 선언한 dq 변수)의 1층에v의 값을 복사한다. (최초 1회)-
현재 dq의 1층에 크기, dq의 레벨(높이), 그리고 최상단 층의 원소 개수를 구한다.
int elem_sz = dq.back().size(); int lev = dq.size(); int base_sz = dq.front().size(); -
회전하게 되면 층의 개수가 늘어나기 때문에 이거에 맞춰 층의 개수를 늘린다.
int increase = elem_sz + 1; while (increase != dq.size()) dq.push_back({}); - 회전 시킨다. dq의
i번째는i번째 층을 의미한다.- 종이에 그려보면 규칙을 찾을 수 있다.
- 규칙
- 가장 상단 층부터 값을 채운다.
- 가장 윗층부터 아래층까지 현재 가장 앞에 있는 값을 넣어준다.
- 그리고 현재 가장 앞에 있는 값을 제거한다.
- 이렇게 하면 값을 일일히 복사하지 않고 관리가 이루어진다!
- deque를 쓰는 이유
int dq_sz = dq.size() - 1; for (int i = 0; i < elem_sz; i++) { for (int j = 0; j < lev; j++) { dq[dq_sz - i].push_back(dq[j].front()); dq[j].pop_front(); } } - 종료 조건
- 그림을 보면 이해가 될 것이다.
- 최하단 길이에서 최상단 길이를 빼준다.
- 이게 층 수보다 작다면, 가장 아래층보다 윗층이 더 길다는 의미이다.
if (base_sz - elem_sz < lev) break;
- 과정 3: 값의 조정
- 단골 유형인 dy, dx이다.
- 인접한 부분에서 동시에 값의 갱신이 이뤄진다.
- 즉, 다시 말해 한번 갱신이 이뤄진 두 정점은 다시 만날 일이 없다는 것이다.
- 그래서 두 방향만 잡고 움직여주면 되는데, 본인은
아래,오른쪽두가지로만 이동시켰다.- visited 배열 필요없음.
const int dy[] = { 1,0 };,const int dx[] = { 0,1 };
-
중간중간 빼주면 값을 변경하는 데 지장이 생기므로 갱신된 값을 임시 변수에 담아 저장했다.
if (ny < dq.size() && nx < dq[ny].size()) { // 맵의 밖을 벗어나지 않았다면, int tmp = abs(dq[y][x] - dq[ny][nx]) / 5 // 갱신할 값을 찾아주고 if (tmp > 0) { // 0보다 크면 저장한다. if (dq[y][x] > dq[ny][nx]) { memo[y][x] -= tmp; memo[ny][nx] += tmp; } else { memo[y][x] += tmp; memo[ny][nx] -= tmp; } } - 위 과정이 끝나면 원래 dq에 갱신시켜주면 된다.
for (int y = 0; y < dq.size(); y++) for (int x = 0; x < dq[y].size(); x++) dq[y][x] += memo[y][x]; - 과정 4 : 평탄화 1
- 평탄화는 규칙에 따라 구현해주면 되는데
- 주의할 점은 평탄화 1번과 2번이 방식이 다르다는 것이다.
- 평탄화 1은 가장 왼쪽에 있는 어항부터, 그리고 아래에 있는 어항부터 가장 위에 있는 어항까지 순서대로 바닥에 놓아야 한다.
- 과정 2에서 떠올렸던 구현 방식을 약간 변형하면 되겠다.
int sz = dq[0].size(); // 최하단의 개수 while(sz--) { for (int i = 0; i < dq.size(); i++) { if (!dq[i].empty()) { v.push_back(dq[i].front()); dq[i].pop_front(); } } } - 과정 5
- 반드시 2개의 층이기 때문에, for문 2개를 써서 임시로 복사한다.
vector<deque<int>> tmp; tmp.push_back({}); tmp.push_back({});- 이후, 반드시 4개의 층으로 구성되므로, 4개의 층을 구성한다.
dq.clear(); for (int i = 0; i < 4; i++) dq.push_back({});- 이후 deque의 성질을 이용해 각 부분을 채워주면 된다.
- 본인은 2개의 분기로 나눠 각각 채웠음.
for (int i = 0; i < tmp.size(); i++) { for (int j = 0; j < sz; j++) { dq[3 - i].push_front(tmp[i].front()); tmp[i].pop_front(); } } for (int i = 0; i < tmp.size(); i++) { for (int j = 0; j < sz; j++) { dq[i].push_back(tmp[i].front()); tmp[i].pop_front(); } } - 과정 6 : 평탄화 2
- 다시 한번 말하지만 처음 평탄화와 규칙이 다르니, 그림을 보고 구현해보자
- 값을 복사할 때 모든 값을 참조하게 되므로, 이 과정에서 최소값 최대값을 미리 계산해두자.
3. 전체 코드
- 각 과정에 대한 출력값을 볼 수 있도록 출력문을 포함시켰다.
- 혹시 본인 코드에 대해 맞왜틀을 시전중이라면, 내 코드의 출력과 비교해보십시오.
- main 함수의 while문에 각 과정에 대해 함수로 하나씩 동작하게 구현하였다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int SZ = 102;
bool vis[SZ][SZ];
vector<int> v;
vector<deque<int>> dq;
int N, K, ans;
const int dy[] = { 1,0 };
const int dx[] = { 0,1 };
void adj() {
vector<int> tmp; // min elem에 대한 index
int cmp = 0x3f3f3f;
for (int nxt : v) cmp = min(cmp, nxt);
for (int i = 0; i < v.size(); i++)
if (cmp == v[i]) tmp.push_back(i);
for (int idx : tmp) v[idx] += 1;
}
void rotate() {
dq.clear();
dq.push_back({});
for (int nxt : v)
dq[0].push_back(nxt);
while (true) {
if (dq.size() == 1) {
dq.push_back({});
dq.back().push_back(dq.front().front());
dq.front().pop_front();
continue;
}
int elem_sz = dq.back().size();
int lev = dq.size();
int base_sz = dq.front().size();
if (base_sz - elem_sz < lev) break;
// 최상단 층에 맞춰 dq size 늘리기
int increase = elem_sz + 1;
while (increase != dq.size()) dq.push_back({});
int dq_sz = dq.size() - 1;
for (int i = 0; i < elem_sz; i++) {
for (int j = 0; j < lev; j++) {
dq[dq_sz - i].push_back(dq[j].front());
dq[j].pop_front();
}
}
}
cout << '\n';
for (int y = 0; y < dq.size(); y++) {
for (int x = 0; x < dq[y].size(); x++) {
cout << dq[y][x] << ' ';
}
cout << '\n';
}
}
void adj2() {
vector<deque<int>> memo;
for (int i = 0; i < dq.size(); i++) {
memo.push_back({});
memo[i].assign(dq[i].size(), 0);
}
for (int y = 0; y < dq.size(); y++) {
for (int x = 0; x < dq[y].size(); x++) {
for (int dir = 0; dir < 2; dir++) {
int ny = y + dy[dir];
int nx = x + dx[dir];
if (ny < dq.size() && nx < dq[ny].size()) {
int tmp = abs(dq[y][x] - dq[ny][nx]) / 5;
if (tmp > 0) {
if (dq[y][x] > dq[ny][nx]) {
memo[y][x] -= tmp;
memo[ny][nx] += tmp;
}
else {
memo[y][x] += tmp;
memo[ny][nx] -= tmp;
}
}
}
}
}
}
for (int y = 0; y < dq.size(); y++)
for (int x = 0; x < dq[y].size(); x++)
dq[y][x] += memo[y][x];
cout << '\n';
for (int y = 0; y < dq.size(); y++) {
for (int x = 0; x < dq[y].size(); x++) {
cout << dq[y][x] << ' ';
}
cout << '\n';
}
}
void flatten() {
v.clear();
int sz = dq[0].size();
while(sz--) {
for (int i = 0; i < dq.size(); i++) {
if (!dq[i].empty()) {
v.push_back(dq[i].front());
dq[i].pop_front();
}
}
}
cout << '\n';
for (int a : v) cout << a << ' ';
cout << '\n';
}
void rotate2() {
vector<deque<int>> tmp;
tmp.push_back({});
tmp.push_back({});
int sz = v.size() / 2;
for (int i = 0; i < sz; i++)
tmp[1].push_front(v[i]);
for (int i = sz; i < v.size(); i++)
tmp[0].push_back(v[i]);
dq.clear();
for (int i = 0; i < 4; i++) dq.push_back({});
sz = tmp[0].size() / 2;
for (int i = 0; i < tmp.size(); i++) {
for (int j = 0; j < sz; j++) {
dq[3 - i].push_front(tmp[i].front());
tmp[i].pop_front();
}
}
for (int i = 0; i < tmp.size(); i++) {
for (int j = 0; j < sz; j++) {
dq[i].push_back(tmp[i].front());
tmp[i].pop_front();
}
}
cout << '\n';
for (int y = 0; y < dq.size(); y++) {
for (int x = 0; x < dq[y].size(); x++) {
cout << dq[y][x] << ' ';
}
cout << '\n';
}
}
int flatten2() {
v.clear();
adj2();
int mx = 0, mn = 0x3f3f3f;
int sz = dq[0].size();
while (sz--) {
for (int i = 0; i < dq.size(); i++) {
int cur = dq[i].front();
v.push_back(cur);
dq[i].pop_front();
mx = max(mx, cur);
mn = min(mn, cur);
}
}
cout << '\n';
for (int a : v) cout << a << ' ';
cout << '\n';
return mx - mn;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K;
for (int a, i = 0; i < N; i++) {
cin >> a;
v.push_back(a);
}
while (true) {
ans++;
adj();
rotate();
adj2();
flatten();
rotate2();
if (flatten2() <= K) break;
}
cout << ans;
return 0;
}