[ 백준 23291 ] 어항정리 (C++)
백준의 어항정리(23291) 문제이다.
( 문제 풀이가 생각보다 많이 길어요... 구현해야 할 것도 많고... 복잡하기도 해서요..!!)
[ 문제풀이 ]
문제가 매우 많이... 조금 더러운 것 같다... 시키는 대로 몇 번의 행동을 했을 때 답을 도출할 수 있냐를 물어보는 것 같다... 해야할 게 너무 많아서 문제를 한 문장으로 요약하기도 쉽지 않은 것 같다...
구현이 전부인 문제이기 때문에 그 과정에서 사용되는 동작방식, 사용하는 자료구조와 같은 부분들은 자신이 가장 편하고 자신있는 부분으로 하면 되지만, 이 글에서는 본인이 사용했던 방법에 대해서 이야기해보고자 한다.
문제를 풀기 위해서 어떤 자료구조와 어떤 자료형으로 필요한 변수들을 선언했는지, 그리고 이 변수들로 어떻게 중간 과정들을 진행했는지 하나하나씩 이야기해보자.
#1. 필요한 정보
필요한 정보라는 타이틀을 만들만큼 사실 필요한 변수들이 많지는 않다. 딱 하나 뿐이다. 바로 "어항"을 어떻게 무슨 자료형으로 어떻게 관리할 것인지에 대해서만 이야기를 해보자.
어항을 어떤 자료형으로 만들지 이야기를 하기 전에 우리가 이 문제에서 앞으로 이 어항으로 뭘 해야 하는지를 이야기 해보자.
이 문제를 구현할 때 우리는 어항으로 다음과 같은 상황들을 구현해야 한다.
1. 물고기 수가 가장 적은 어항에 물고기 추가하기
2. 어항 회전시키면서 공중부양 시키기
3. 공중부양 시킨 어항 다시 펼치기
4. 또 다른 방식으로 공중부양 시키기
5. 물고기 수 조절하기
6. 다시 펼치기
뭐 이렇게 6가지 기능을 구현해야 한다. 그런데 딱 봐도 1번은 어떤 자료형을 사용하던지 크게 상관이 없을 것 같다.
그냥 모든 어항을 탐색하면서 물고기 수가 가장 적은 곳만 찾아서 더해주기만 하면 된다.
하지만 ! "Index 접근이 가능한 자료구조" 라면 더 좋을 것 같다. 왜냐하면, Index를 저장할 수 없다면 전체 어항을 탐색하면서 물고기가 가장 적은 어항들을 찾고, 다시 한번 탐색하면서 그 가장 적은 어항들에게 물고기를 추가해줘야 하기 때문이다.
뭐, 이렇게 하더라도 상관은 없지만 Index로 접근을 할 수 있다면, 가장 적은 어항들을 찾을 때, 해당 어항들의 Index번호만 저장해 놓고 해당 Index에 바로 접근해서 물고기를 추가해주기만 하면 되기 때문이다.
그 다음은 2 , 4번과 3 , 6을 통일 시켜서 생각을 해보자. 어차피 2, 4번은 방식은 약간 다르지만 결국 어항을 회전시키면서 공중부양 시켜야 되는 부분이고, 3 , 6번은 공중부양된 어항들을 다시 펼치는 기능이기 때문이다.
먼저, 어항을 회전시키면서 공중 부양을 시키는 과정을 생각해보자.
우리가 문제에서 읽은 그림처럼 저렇게 세로로 여러줄을 쌓는 그림을 코드로 표현하려면... 어떤 방법이 가장 좋을까..???
본인은 가장 먼저 2차원 배열을 생각했었다. 2차원 배열을 통해서 마치 하나의 맵 처럼 표현을 하고, 어항이 위로 쌓일 때 마다 실제 그림처럼 위로는 쌓지 못하지만 2차원 배열에서 그 다음 행에다가 데이터를 추가해주면 아래로 쌓이는 것 처럼 보이겠지만 어항을 공중부양 시키는 과정은 표현할 수 있을 거라 생각했다. 2차원 배열로 이 과정을 정말 대략적으로 그려보면 다음과 같이 그려질 것이다.
가장 초기 상태를 위의 그림과 같이 그리게 되면 어항이 다음과 같이 쌓이는 것이다.
위의 그림들과 같이 저렇게 아래쪽으로 쌓이게 되는 것이다. 그런데 가장 큰 단점이 하나 있다.
따로 시작점을 관리를 해주거나, 어항을 쌓을 때 마다 전체 배열을 옮기거나 둘 중 하나를 해줘야 한다는 것이다.
위의 그림에서 연한 회색들로 채워져 있는 어항들을 보자. 저 어항들은 이미 쌓여서 더 이상 가장 아래층(0행)에 존재하지 않는 어항들이다. 그리고 쌓여감으로 인해서 사라지는 어항들 때문에 배열의 시작점이 바뀌게 될 것이다.
이러한 부분들에 대해서 관리를 따로 해주어야 한다는 단점이 있다. 하지만, 1번 구현사항에서 이야기 했듯이 "Index에 접근"도 배열은 용이한 편이기 때문에 일단은 첫 번째로 "2차원 배열"을 생각해볼 수 있는 것 같다.
이 외에 Queue , Vector , list와 같은 자료구조들을 생각해 봤는데 Queue같은 경우에는 Index접근도 안되고 데이터의 삽입 삭제가 가장 앞과 뒤에서 밖에 할 수 없다는 점, Vector는 Index접근은 가능하지만 데이터의 삽입 삭제가 가장 뒤에서만 일어날 수 있다는 점(물론 erase함수를 사용하면 중간 삭제도 가능은 함..), list 같은 경우에는 Index접근이 되지 않는다는 점 등의 단점들이 있어서 별로 내키지 않았다.
그래서 배열로 하려고 보니 위에서 언급한 배열이 가지는 단점들 때문에 또 다른 방법을 생각하게 되었다.
결국 본인은 "Deque" 자료구조를 이용해서 어항을 관리해 주었다.
Deque에 대해서 간단하게만 이야기해보자면, Queue와는 다르게 Index의 접근이 가능한 자료구조이다. 즉, 우리가 이야기한 1번 구현사항을 만족하는 자료구조이다. 두 번째로, 데이터의 삽입과 삭제가 앞 뒤로 자유자재로 가능하다.
우리가 배열로 하게 되면 데이터를 삽입할 때 시작점을 따로 관리해 주거나, 실제로 삭제를 해버리고 전체 배열을 앞땡기거나 뒤로 밀거나 하는 과정이 필요하다고 이야기했는데, 이 과정을 이렇게 하는것이 아닌 Deque를 통해서 실제로 데이터를 삭제해버리고 그 다음 행에 삽입을 해버리는 식으로 생각을 한 것이다. 이렇게 되면 배열처럼 시작점을 관리한다거나 전체 데이터를 미루고 땡기고 하는 과정 또한 필요가 없어지게 된다.
데이터의 삽입 삭제가 앞/뒤에서 자유자재 가능하냐 아니냐 이런 이야기를 아까부터 계속 하고 있는데 이 부분에 대한 이야기는 밑에서 각각의 단계별로 이야기를 하면서 구체적으로 이야기해보자. 결국 ! 본인은 Deque로 어항들을 관리해 주었고 Deque 배열을 통해서 어항이 쌓이는 과정들을 대비해 주었다.
#define MAX 110
deque<int> bowl[MAX];위와 같이 deque 배열을 선언해놓고 1층을 0번 Index로 그리고 어항이 쌓이면 쌓일수록 위의 배열 그림과 같이 1번, 2번, 3번 Index 순으로 계속해서 값을 넣으면서 쌓아갈 것이다.
#2. 어항에 물고기 추가하기
이제부터 본격적으로 각 과정들에 대해서 이해해보도록 하자.
가장 먼저, 물고기를 추가하는 과정을 진행해보자. 이 부분은 간단하다. 모든 어항이 다 펼쳐진 한 줄로만 이루어진 상태에서는 어항은 0번 Index에 밖에 존재하질 않는다. 따라서, deque의 0번 Index에 접근해서 모든 어항을 탐색하면서 물고기의 수를 카운팅 하면서 가장 적은 어항의 Index번호를 저장한 후에 물고기를 추가해 주었다. 코드로 나타내면 다음과 같다.
void addFish() {
int minFish = 987654321;
vector<int> idxV;
for (int i = 0; i < bowl[0].size(); i++) {
if (bowl[0][i] < minFish) {
minFish = bowl[0][i];
idxV.clear();
idxV.push_back(i);
} else if (bowl[0][i] == minFish) {
idxV.push_back(i);
}
}
for (auto idx : idxV) {
bowl[0][idx]++;
}
}
#3. 어항 쌓기
이 문제에서 가장 골치 아픈 부분이라고 생각한다.. 본인은 그랬기 때문이다.
먼저 어항을 쌓는 법에 대해서 다시한번 이야기를 해보고 시작하자.
1. 가장 왼쪽에 있는 어항을 그 어항의 오른쪽 어항 위에 올려놓는다.
2. 2개 이상 쌓여있는 어항을 모두 공중부양 시킨 후, 시계방향으로 90도 회전시킨다.
3. 90도 회전시킨 어항들을 바닥에 있는 어항의 위에 올려놓는다.
4. 위의 과정을 공중부양 시킨 어항들을 쌓았을 때, 바닥에 어항이 있을 때 까지 반복한다.
그럼 한번 그림으로 나타내면서 같이 한번 진행해보자.
위와 같이 어항이 존재한다고 생각해보자.
가장 처음에 공중 부양 시켜야 될 어항에 대해서 이야기를 해보자. 위의 그림에서 'A' 어항이 될 것이다.
그리고 이 때, 공중부양 시켜야 할 어항의 크기에 대해서 생각을 해보면 다음과 같다.
바로 가로의 길이 = 1 , 세로의 길이 = 1 인 어항을 공중 부양 시켜야 하는 상황이다.
그럼 공중부양 시켜서 90도 회전 후 올리게 되면 다음과 같이 된다.
이 다음 턴에 공중 부양을 시켜야 될 어항들의 크기를 한번 살펴보면 다음과 같다.
(가로의 길이 , 세로의 길이) 가 (1 , 1)에서 (1 , 2)로 바뀌게 되었다.
그리고 90도 회전 시킨 후 어항을 올리게 되면 다음과 같아진다.
위와 같이 될 텐데 이제 이 다음 턴에서 공중 부양 시켜야 할 어항의 크기를 살펴보자.
(가로의 길이 , 세로의 길이) 가 (1 , 2)에서 (2 , 2)로 바뀌게 되었다.
마지막으로 한번만 더 해보자. 이 상태에서 저 4개의 어항을 공중부양 시킨 후 , 90도 회전 시켜서 올리게 되면 다음과 같아진다.
(가로의 길이 , 세로의 길이)가 (2 , 3)으로 바뀌게 되었다. 그리고 우리는 더 어항을 쌓을 수가 없다. 그럼 지금까지 어항을 쌓아가면서 크기를 계속해서 적어보았는데 이를 정리해서 한번 살펴보자.
쌓아야 할 어항의 (가로의 길이 , 세로의 길이) 가
(1 , 1) - (1 , 2) - (2 , 2) - (2 , 3) ... 의 순서로 바뀌게 되는 것을 확인했다. 우리는 여기서 규칙을 하나 찾을 수 있다.
각 턴이 진행됨에 따라 순차적으로 세로의 길이 + 1 , 가로의 길이 + 1 , 세로의 길이 + 1 , 가로의 길이 + 1 ... 의 패턴을 가지고 있다는 것을 알 수 있다. (1 , 1)에서 세로의 길이가 + 1 됨에 따라 (1 , 2)가 되었고, 이 상태에서 가로의 길이가 + 1 됨에 따라 ( 2 , 2)가 되었고 이 상태에서 세로의 길이가 + 1 됨에 따라 (2 , 3)이 되었다. 이런식의 규칙을 가지고 있다.
그런데 이 가로와 세로의 길이가 늘어난다는 규칙은 알겠는데 이를 어디다가 써먹을 수 있을까 ??
1. 어항을 더 이상 쌓지 못하는 순간에 대한 계산을 할 수 있다. 즉, 기저조건에 대해서 쉽게 파악할 수 있다.
더 이상 어항을 쌓지 못하는 순간을 어떻게 계산할 수 있을까 ?? 가장 위에 있는 가로의 길이 = 2 , 세로의 길이 = 3 인 순간을 한번 살펴보자. 저 상황에서 더 이상 어항을 쌓지는 못하게 된다. 이를 가로의 길이와 세로의 길이를 통해서 어떻게 알 수 있을까 ??
"더 이상 어항을 쌓을 수 있냐 없냐" 는 문제에서 제시한 바에 따르면 "쌓은 모든 어항 아래에 어항이 존재하냐 안하냐" 로 파악을 할 수 있고, 어항을 쌓게 될 때 쌓은 모든 어항 아래에 어항이 존재하는지 안하는지는 "쌓을 어항의 가로 길이보단 세로 길이에 영향" 을 미치게 된다. 왜냐하면 어항을 "90도로 회전 시킨 후, 어항을 쌓기 때문" 이다. 이를 쉽게 이해하기 위해서 위의 그림을 조금만 수정해보자.
위와 같이 되어있었다면 어항을 더 쌓을 수 있었을 것이다. 다음과 같이 !
쌓게 되면 쌓기 전에 세로의 길이였던 3이 쌓은 후에 가로의 길이인 3이 된다. 즉 ! 쌓을 어항의 세로 길이가 쌓은 후의 가로 길이가 되기 때문에 우리는 아래에 어항이 존재하는지는 쌓을 어항의 세로 길이로 판단할 수 있다. 어떻게 ??
위의 그림을 우리가 표현하고 있는 Deque로 나타내보면 다음과 같은 상태이다.
Deque[0] = { E , F , G , H }
Deque[1] = { D , A }
Deque[2] = { C , B }
그리고 어항을 쌓게 되면 Deque[0]에서 "2개" 가 빠지게 되고, 쌓은 어항의 가로길이는 현재의 세로길이인 "3"이 된다.
즉, Deque[0]의 현재 길이인 '4'에서 쌓을 어항의 가로 길이인 "2"만큼 감소한 값이 현재의 세로길이인 "3"보다 작기 때문에 더 이상 어항을 쌓을 수 없다는 것을 알 수 있다.
정리해보면.. Deque[0].size() - width < height 인 경우에 더 이상의 어항을 쌓을 수 없다는 것이다. 우리는 이렇게 가로와 세로 길이를 통해서 어항을 더 이상 쌓을 수 있는지 없는지를 판단할 수 있다. 이를 코드로 나타내면 다음과 같이 표현이 가능하다.
bool canBuild(int w, int h) {
if (bowl[0].size() - w < h) {
return false;
}
return true;
}
2. 공중 부양 시킨 후 90도 회전 시켜서 쌓기
가로와 세로 길이를 통해서 이 과정 또한 접근을 할 수가 있다. 물론 머리가 조금 아픈 부분이긴 하다.
위의 경우로 진행을 해보자.
현재 상태를 Deque의 Index번호로 나타내면 위의 그림과 같을 것이다.
그리고 이해하기 쉽게 어항을 90도 회전시킨 후 결과 그림도 한번 보면서 이야기를 해보자.
잘 보면 다음과 같이 움직였다는 것을 확인할 수 있다.
빨강색 테두리들이 저렇게 움직였고 파랑색 테두리 어항들이 저렇게 움직였다.
저렇게 움직인게 어떻게 움직인건지는 모르겠지만 뭔가 쭉 연결된 채로 움직인 거 같다는 느낌이 들기는 한다.
보다 조금만 더 구체적으로 이야기를 해보면.... 각 층의 0번째에 위치한 어항들이 가장 높은 층에 쌓이게 되고, 그 다음 번으로 순차적으로 넘어갈 때마다 한 층이 층수가 낮아지게 된다.
왼쪽 그림에서 빨강색 테두리 어항들은 각각 0층 1층 2층에서 0번째에 위치한 어항들이고 이 어항들이 가장 높은 층수인 2층으로 쌓이게 되었다. 파랑색 테두리 어항들은 각각 0층 1층 2층에서 1번째에 위치한 어항들이고 이 어항들이 그 다음 번으로 높은 층수인 1층으로 쌓이게 되었다. 그럼 여기서 "가장 높은 층수"를 어떻게 구할 수 있을까 ???
아까 우리가 어항을 더 이상 쌓지 못하는 경우를 계산할 때, 어항이 90도로 회전한 후에 쌓이기 때문에 "쌓을 어항의 세로 길이가 쌓고난 후의 가로길이가 된다. 따라서 쌓을 어항의 세로 길이가 중요하다" 라는 이야기를 했었다.
여기서는 가장 높은 층수를 구해야 하니까, 즉, 쌓고난 후의 세로 높이를 구해야 하는 것이니까 반대로 쌓기 전의 가로의 길이를 보면 된다. 위의 그림에서 어항을 쌓기 전에 쌓을 어항들의 가로의 길이 '2'이다. 그리고 가장 높은 층수는 '2'층이다.
즉, 0번째에 위치한 어항들은 쌓을 어항의 가로의 길이 층에 위치, 1번째에 위치한 어항들은 쌓을 어항의 가로의 길이 - 1층에 위치... 이런식의 패턴이 존재한다. 그리고 어항이 쌓이는 순서는 0층부터 순차적으로 올라가게 된다. 위의 그림에서 0층 0번에 있는 'E'가 2층의 0번 Index로 들어가게 되었다. 그리고 그 이후에 순차적으로 1층에 있는 'D'가 그 이후에 2층에 있는 'C'가 들어간 것을 확인할 수 있다.
너무 내용이 난잡하니까 정리를 한번 해보자.
* 어항을 쌓을 때의 규칙을 가로의 길이와 세로의 길이를 통해서 구해보았다.
* 그 규칙은, 각 층의 0번째 Index에 위치해 있는 어항들이 낮은 층수에 있는 어항들부터 순차적으로 가장 높은 층수
에 쌓이게 된다.
* Index의 값이 증가할 수록, 어항이 쌓이는 층수는 감소하게 된다.
어느정도 정리를 해보면 위와 같이 정리를 해볼 수 있을 것 같다. 이를 코드로 나타내면 다음과 같다.
int tmpWidth = width;
for (int i = 0; i < width; i++, tmpWidth--) {
int idx = 0;
for (int j = 0; j < height; j++, idx++) {
bowl[tmpWidth].push_back(bowl[idx][i]);
}
}이게 어항을 쌓는 과정이다. line 5)에 있는 for문에서는 쌓을 어항의 세로의 길이만큼 반복을 하는데, 위에서 이야기 했듯이 가장 낮은 층수에 있는 어항들부터 순차적으로 쌓이게 된다. 그리고 층수가 가장 낮은 어항들부터 차례대로 넣기 위해서 push_back()을 통해서 뒤쪽에 어항들을 넣어주고 있다.
그리고 tmpWidth라는 변수가 "쌓을 어항의 가로의 길이"를 저장하고 있는 변수인데, 이 값을 통해서 몇 층에 어항을 쌓아야 하는지를 파악할 수 있다. 그리고 이 값은 Index값이 증가할수록 감소하는 것을 확인할 수 있다.
그럼 이 상황에서 위의 코드를 적용시켰다고 가정해보자. 그럼 어떻게 될까 ?? 우리가 원하는 그림이 나올까 ?? 아마, 이 상태에서 위의 코드를 적용시키면 다음과 같이 나올 것이다.
왜 위와 같이 나오게 될까 ?? 위의 코드에서는 그 어디에도 데이터를 삭제하는 코드가 존재하질 않는다. push_back()만 존재할 뿐, pop_과 관련된 그 어떠한 코드가 존재하지를 않는다. 그렇기 때문에 위와 같이 될 것이다.
즉 ! 우리가 그림으로 나타냈을 때는 어항을 진짜로 딱 떼어내서 공중부양 시켜서 회전시키는 것처럼 표현을 할 수 있었지만 이를 코드로 구현할 때에는 실제로 그 부분을 떼내고 그런 과정을 진행하지 않았기 때문에 "기존의 어항들이 아직 남아있는 상황" 이 발생한 것이다. 그럼 이제 어항을 쌓았으니 쌓은 어항들의 기존의 상태는 삭제를 시켜주자. 위의 그림에서 우리는 딱 이부분만 없애주면 된다.
딱 빨강색 테두리 부분만 지워주면 되는데 이는 각 층수별로 "쌓을 어항의 가로의 길이"만큼만 삭제를 시켜주면 된다.
위의 그림에서는 쌓을 어항의 세로 길이가 "3", 가로 길이가 "2" 였으니까, 0부터 3개의 층수인 0, 1, 2층에서 가로의 길이인 2개씩 데이터를 삭제해주면 된다. 저걸 어떻게 삭제할 수 있을까 ??
여기서 Deque의 장점이 하나 나오게 된다. 우리가 어항을 쌓을 때는 push_back()을 통해서 어항을 쌓았지만, Deque같은 경우에는 삽입 / 삭제가 앞뒤로 자유자재로 가능하다. 즉, 이 때는 pop_front()를 통해서 데이터를 삭제 시켜줄 수가 있다.
그래서 위의 코드에서 다음과 같은 부분이 추가되어야 한다.
int tmpWidth = width;
for (int i = 0; i < width; i++, tmpWidth--) {
int idx = 0;
for (int j = 0; j < height; j++, idx++) {
bowl[tmpWidth].push_back(bowl[idx][i]);
}
}
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
bowl[i].pop_front();
}
}이렇게 되어야 우리가 원하는 그림이 나오게 되는 것이다. 그럼 어항을 쌓는 과정에 대한 구현이 90% 이상 끝나게 된다.
정리해보고 어항을 쌓는 부분에 대한 최종코드를 살펴보자.
"쌓을 어항의 (가로의 길이 , 세로의 길이) 는 세로의 길이 + 1 , 가로의 길이 + 1 이 반복되는 패턴이 있다."
"어항을 쌓는 과정의 종료 조건은 [ 어항의 0층의 길이 - 쌓을 어항의 가로 길이 < 쌓을 어항의 세로 길이 ] 로 판단"
"어항을 쌓는 과정은 "각 층의 0번째 데이터들부터 가장 높은 층수(쌓을 어항의 가로 길이)에 쌓이게 된다"
"어항을 쌓는 과정은 push_back()을 통해서 각각 적절한 층수에 데이터를 삽입하게 된다"
"어항을 다 쌓았다면, 쌓기 전의 어항들은 삭제해줘야 하므로 이 때에는 pop_front()를 통해서 삭제한다"
int buildBowl() {
int width = 1;
int height = 1;
bool flag = false;
while (1) {
if (canBuild(width, height) == false) {
break;
}
int tmpWidth = width;
for (int i = 0; i < width; i++, tmpWidth--) {
int idx = 0;
for (int j = 0; j < height; j++, idx++) {
bowl[tmpWidth].push_back(bowl[idx][i]);
}
}
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
bowl[i].pop_front();
}
}
if (flag == false) {
height++;
flag = true;
} else {
width++;
flag = false;
}
}
return height;
}
#4. 어항 펼치기
이제 어항을 펼치는 과정을 진행해보자. 먼저 어항을 쌓을 때 처럼 어떤 규칙에 의해서 어항이 펼쳐지는지 부터 살펴보자.
그리고 어항 펼치기는 이 하나의 방법만 사용할 것이다. 어항을 쌓는 과정이 총 2개가 있다. 우리는 그 중에서 한 가지 과정을 #3에서 이야기 해보았고 어항을 펼친 후, 다시 한번 어항을 쌓는 과정이 생기게 된다. 그리고 그 쌓은 어항을 다시한번 펼쳐야 하는 과정이 필요한데 어항을 쌓는 과정은 2개의 과정이 다르기 때문에 각각 별도로 구현해야 하지만, 펼치는 것은 하나의 코드로도 해결이 가능하다. 따라서 지금부터 하는 이야기 한 가지 방법으로 어항을 펼치는 모든 부분을 이 방법으로 끝낼 것이다.
위와 같이 어항이 쌓여있다고 가정해보자. 이 어항을 펼치게 되면 다음과 같아진다.
위와 같이 어항이 펼쳐지게 되는데 다음과 같은 규칙을 찾을 수 있다.
위의 그림과 같이 어항이 펼쳐지게 되는데 이를 정리해보면 다음과 같이 표현할 수 있다.
"0층부터 순차적으로 층수를 올라갈 때, 각 층의 K번째 Index에 있는 어항들부터 순차적으로 펼쳐진다".
위의 그림을 보게 되면 0층의 0번 Index에 있는 'A'가 가장 앞에 펼쳐져 있고 그 다음으로는 1층의 0번 Index에 있는 'B'가 펼쳐져 있고 그 다음으로는 2층의 0번 Index에 있는 'C'가 펼쳐지게 된다.
그 다음으로는 0층의 1번 Index에 있는 'D'가, 1층의 1번 Index에 있는 'E'가, 1층의 2번 Index에 있는 'F'가 펼쳐지게 된다.
우리는 문제 초반부부터 계속해서 이야기한 "어항의 가로의 길이와 세로의 길이" 에 대해서 계속해서 계산을 하고 있고 그 값들이 얼마인지 계산을 해 왔다. 위의 그림에서도 생각을 해보자. 위의 그림에서는 더 이상 어항을 쌓을 수는 없지만 쌓을 어항의 가로의 길이와 세로의 길이를 보면 (가로의 길이 = 2 , 세로의 길이 = 3) 이 된다. 그리고 그림과 이 길이들을 보면 "세로의 길이번을 가로의 길이 만큼 반복" 한다는 것(?)을 알 수 있다. (펼쳐지는 어항이 결국 6개이니, 세로의 길이인 3개의 어항이 2번만큼 반복된 6개의 어항이 펼쳐진다는 의미...)
어항을 펼칠 때는 0층에다가 데이터를 넣어주기만 하면 된다. 그럼 코드로 나타내면 다음과 같이 표현할 수 있다.
void spreadBowl(int height) {
int width = bowl[height - 1].size();
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
bowl[0].push_back(bowl[j][i]);
}
}
}그럼 위의 코드를 실행시키면 어떤 결과가 나오게 될까 ?? 어항을 쌓을 떄와 비슷한 현상이 일어나게 된다.
위의 코드를 실행하면 다음과 같은 결과가 나오게 된다.
아마 이와 같은 현상이 일어나게 될 것이다. 왜냐하면 위의 코드에서는 데이터를 쌓는 과정만 존재하지 기존의 어항을 빼는 과정은 존재하지 않기 때문이다. 그럼 일단 쉬운것부터 해보자. 일단 0층을 제외하고는 모두 clear() 를 시켜주면 될 것이다.
그럼 위의 그림에서 위쪽에 있는 그림처럼 표현이 될 것인데, 우리는 아래에 있는 그림처럼 표현이 되도록 만들어야 한다.
그런데 가장 신경쓰이는게 'G'와 'H'이다. 저 친구들을 어떻게 해줘야 할까 ???
본인은 이 과정을 위해서 "기존의 0층의 size"를 계산해 놓았다. 여기서 기존의 size라는 것은 다음을 의미한다.
기존의 0층의 크기는 '4'였고 그 중에서 우리가 쌓을 어항의 가로의 길이는 '2'였다.
우리는 이 2개의 값으로 'G'와 'H'에 접근을 할 수가 있다. 바로 다음과 같은 코드로 접근이 가능하다.
for (int i = width; i < size; i++) {
bowl[0].push_back(bowl[0][i]);
}이렇게 되면 모양이 다음과 같이 변하게 될 것이다.
위와 같이 가장 뒤에 'G'와 'H'가 붙게 되는 것이다. 그럼 가장 앞에 있는 저 4개의 알파벳들만 지워주면 되는데, Deque의 장점으로는 pop_front()가 가능하다는 것이다. pop_front()를 위에서 구한 "기존의 0층 크기" 만큼 반복해주면 4개가 사라지게 될 것이다.
모든 내용을 정리해보면 어항을 펼치는 소스코드는 다음과 같다.
void spreadBowl(int height) {
int width = bowl[height - 1].size();
int size = bowl[0].size();
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
bowl[0].push_back(bowl[j][i]);
}
}
for (int i = 1; i < height; i++) {
bowl[i].clear();
}
for (int i = width; i < size; i++) {
bowl[0].push_back(bowl[0][i]);
}
for (int i = 0; i < size; i++) {
bowl[0].pop_front();
}
}
#5. 물고기 수 조절하기
이제 어려운 과정은 다 끝났다.. 물고기 수를 조절하는 과정은 인접한 모든 칸에 대해서 동시에 일어나기 때문에 동/서/남/북 4방향을 탐색해야 하는 것 같지만 본인은 2가지 방향만 진행해 주었다.
위의 그림에서 빨강색 네모친 2개의 어항을 보자.
과연 "C를 기준으로 남쪽 방향에 있는 B와 비교 해서 물고기 수를 조절하는 과정" 과 "B를 기준으로 북쪽 방향에 있는 C와 비교 해서 물고기 수를 조절하는 과정" 이 2가지 과정이 모두 필요할까 ?? 그렇지 않다. 둘 중 어느 하나의 과정만 진행하더라도 B와 C 사이의 물고기 수를 조절하는 과정은 끝나게 된다.
마찬 가지로 C와 F를 조절할 떄에도 어느 한 가지 방향으로만 해주면 된다.
그래서 본인은 각 어항들을 기준으로 동쪽과 남쪽 2가지 방향만 진행해 주었다. 그리고 진행을 할 때에는 tempBowl을 하나 만들어서 임시 저장 공간에 변경된 값을 저장한 후에 다시 원본 맵에 적용시켜 주었다.
원본 맵에 바로 적용을 시키게 되면 계산이 제대로 되지 않는 문제가 발생할 수 있기 때문이다.
void adjustFish(int height) {
deque<int> tmpbowl[MAX];
for (int i = 0; i < height; i++) {
tmpbowl[i] = bowl[i];
}
for (int i = height - 1; i >= 0; i--) {
for (int j = 0; j < bowl[i].size(); j++) {
int x = i;
int y = j;
int num = bowl[x][y];
for (int k = 0; k < 2; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx >= 0 && ny < bowl[i].size()) {
int num2 = bowl[nx][ny];
int diff = abs(num - num2) / 5;
if (diff > 0) {
if (num > num2) {
tmpbowl[x][y] -= diff;
tmpbowl[nx][ny] += diff;
} else {
tmpbowl[nx][ny] -= diff;
tmpbowl[x][y] += diff;
}
}
}
}
}
}
for (int i = 0; i < height; i++) {
bowl[i] = tmpbowl[i];
}
}
#6. 어항 펼치기
이 부분은 안해도 된다. #4에서 이미 다 끝내놓았기 때문이다 !
이런 과정들을 통해서 문제를 해결할 수가 있다.... 모든 과정을 간단하게 정리 한번 해보자. 너무 길기도 했고 복잡하기도 했다.
# 우리는 어항을 'Deque'로 관리 ! Deque배열을 선언해서, 배열의 Index를 각각의 층으로 생각.
# 각각의 층이 필요한 이유 = 어항이 쌓이는 과정과 펼쳐지는 과정이 있기 때문에 !
# 어항을 쌓을 때는 가장 먼저 가로의 길이와 세로의 길이를 파악하고 이 길이들의 규칙을 파악했다.
# 어항을 쌓는 과정 , 쌓는 것이 종료되는 시점 등 모든 과정을 "가로의 길이와 세로의 길이"로 알 수 있다.
# 어항을 펼치는 과정 또한 가로의 길이와 세로의 길이를 통해서 계산을 진행할 수 있다.
# 물고기의 수를 조절하는 과정은, 4가지 방향이 아닌 동/남 2가지 방향으로만 진행해준다.
[ 소스코드 ]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
|
#include <iostream>
#include <queue>
#include <vector>
#define MAX 110
using namespace std;
int n, k;
deque<int> bowl[MAX];
int dx[] = { 0, -1 };
int dy[] = { 1, 0 };
void input() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
int a; cin >> a;
bowl[0].push_back(a);
}
}
bool check() {
int minFish = 987654321;
int maxFish = -987654321;
for (int i = 0; i < bowl[0].size(); i++) {
minFish = min(minFish, bowl[0][i]);
maxFish = max(maxFish, bowl[0][i]);
}
return maxFish - minFish <= k ? true : false;
}
void addFish() {
int minFish = 987654321;
vector<int> idxV;
for (int i = 0; i < bowl[0].size(); i++) {
if (bowl[0][i] < minFish) {
minFish = bowl[0][i];
idxV.clear();
idxV.push_back(i);
} else if (bowl[0][i] == minFish) {
idxV.push_back(i);
}
}
for (auto idx : idxV) {
bowl[0][idx]++;
}
}
bool canBuild(int w, int h) {
if (bowl[0].size() - w < h) {
return false;
}
return true;
}
void print() {
for (int i = 0; i < 5; i++) {
if (bowl[i].size() == 0) continue;
for (int j = 0; j < bowl[i].size(); j++) {
printf("%2d ", bowl[i][j]);
}
cout << endl;
}
cout << endl;
}
int buildBowl() {
int width = 1;
int height = 1;
bool flag = false;
while (1) {
if (canBuild(width, height) == false) {
break;
}
int tmpWidth = width;
for (int i = 0; i < width; i++, tmpWidth--) {
int idx = 0;
for (int j = 0; j < height; j++, idx++) {
bowl[tmpWidth].push_back(bowl[idx][i]);
}
}
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
bowl[i].pop_front();
}
}
if (flag == false) {
height++;
flag = true;
} else {
width++;
flag = false;
}
}
return height;
}
void adjustFish(int height) {
deque<int> tmpbowl[MAX];
for (int i = 0; i < height; i++) {
tmpbowl[i] = bowl[i];
}
for (int i = height - 1; i >= 0; i--) {
for (int j = 0; j < bowl[i].size(); j++) {
int x = i;
int y = j;
int num = bowl[x][y];
for (int k = 0; k < 2; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx >= 0 && ny < bowl[i].size()) {
int num2 = bowl[nx][ny];
int diff = abs(num - num2) / 5;
if (diff > 0) {
if (num > num2) {
tmpbowl[x][y] -= diff;
tmpbowl[nx][ny] += diff;
} else {
tmpbowl[nx][ny] -= diff;
tmpbowl[x][y] += diff;
}
}
}
}
}
}
for (int i = 0; i < height; i++) {
bowl[i] = tmpbowl[i];
}
}
void spreadBowl(int height) {
int width = bowl[height - 1].size();
int size = bowl[0].size();
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
bowl[0].push_back(bowl[j][i]);
}
}
for (int i = 1; i < height; i++) {
bowl[i].clear();
}
for (int i = width; i < size; i++) {
bowl[0].push_back(bowl[0][i]);
}
for (int i = 0; i < size; i++) {
bowl[0].pop_front();
}
}
void buildBowl2() {
int n = bowl[0].size();
for (int i = 0; i < n / 2; i++) {
bowl[1].push_front(bowl[0][i]);
}
for (int i = 0; i < n / 2; i++) {
bowl[0].pop_front();
}
for (int i = 0; i < n / 4; i++) {
bowl[2].push_front(bowl[1][i]);
bowl[3].push_front(bowl[0][i]);
}
for (int i = 0; i < n / 4; i++) {
bowl[0].pop_front();
bowl[1].pop_front();
}
}
void solution() {
int answer = 0;
while (1) {
if (check() == true) {
cout << answer << endl;
break;
}
addFish();
int height = buildBowl();
adjustFish(height);
spreadBowl(height);
buildBowl2();
adjustFish(4);
spreadBowl(4);
answer++;
}
}
void solve() {
input();
solution();
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("input2.txt", "r", stdin);
solve();
return 0;
}
|
cs |