가상의 퍼즐게임에 들어갈 코드를 만들어 보자. 이 퍼즐게임의 게임판은 N×N의 크기이고, 게임판의 각각의 칸은 빈칸이거나, 특정 색의 1×1 크기인 정사각형 블럭이 놓여 있다.
= 원래 게임판
이것이 게임판의 초기 상태이다. 이 게임판을 오른쪽으로 90도 돌리면 아래와 같은 모양이 될 것이다.
이 블럭들을 모두 아래쪽으로 끝까지 밀어놓으면 아래와 같은 모양이 된다.
= SpinAndSlide(원래 게임판, 1)
'게임판을 오른쪽으로 90도 회전한 뒤, 블럭들을 모두 아래쪽으로 끝까지 미는' 동작을
SpinAndSlide 라고 정의하자. 주어진 게임판에 SpinAndSlide를 여러번 적용했을 때 그 결과가 어떻게 될지를 알아내 보자.예를 들어, 바로 위 그림에
SpinAndSlide를 한 번 더 적용한 결과는 아래와 같다.
= SpinAndSlide(원래 게임판, 2)
입력
첫번째 줄에 게임판의 크기를 나타내는 �N이 주어진다. �N은 1 이상 100 이하의 정수이다.
두번째 줄에
SpinAndSlide를 몇 번 적용할지를 나타내는 �M이 주어진다. �M은 0 이상 100이하의 정수이다.세번째 줄부터 �N개의 줄에 걸쳐 게임판의 초기 상태가 주어지는데, 각 줄은 (개행문자를 제외하고) �N개의 문자로 이루어져 있다. 각 문자는, 각 칸에 블럭이 들어있는 경우 블럭의 색을 나타내는 알파벳 대문자이며, 빈칸인 경우
. 이다.게임판의 초기 상태는 블럭들을 모두 아래쪽으로 밀어놓은 상태이다.
출력
게임판의 초기 상태에
SpinAndSlide를 �M회 적용한 결과를, �N개의 줄에 걸쳐 출력한다. 각 줄은 (개행문자를 제외하고) �N개의 문자로 이루어져야 한다. 각 칸에 블럭이 들어있는 경우 블럭의 색을 나타내는 알파벳 대문자를, 빈칸인 경우 . 을 출력한다.예제
입력
7 2 ....... ....... ...A... ...B... ..ACA.. ..BBB.. .AAAAA.
출력
....... ....... A...... B...... AAA.... BBB.... ACAAA..
풀이
#include<iostream> #include<algorithm> #include<vector> #include<queue> #include <list> #include<map> using namespace std; #define MAX 101 int N; char _map[MAX][MAX]; int spinCount = 1; void Input() { cin >> N; cin >> spinCount; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> _map[i][j]; } } } char rotatedMap[MAX][MAX]; void rotate() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { rotatedMap[j][N - 1 - i] = _map[i][j]; } } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { _map[i][j] = rotatedMap[i][j]; } } } void slide() { for (int j = 0; j < N; j++) { int emptyIndex = N - 1; for (int i = N - 1; i >= 0; i--) { if (_map[i][j] != '.') { _map[emptyIndex--][j] = _map[i][j]; if (emptyIndex != i) _map[i][j] = '.'; } } } } void Solution() { while (spinCount > 0) { spinCount--; rotate(); slide(); } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cout << _map[i][j]; } cout << '\n'; } } void Solve() { Input(); Solution(); } int main() { Solve(); }
우선 위 문제는 2 가지로 방향으로 따로따로 풀어봐야 한다.
90도로 회전 하는 것과 아래로 밀어내는 것.
우선 회전하는 곳 부터 풀이하고자 한다.
회전
우선 문제를 풀이하기 위해선 90도로 회전 했을 때 Y,X값이 어떻게 변화 하는 지를 분석했어야 했다.
회전하기 전 이미지 중 원을 친 부분의 현재 좌표 값은 (2,3) 이고, 회전 후 에는 (3,4)가 된다.
바로 그 아래 초록색 박스의 좌표도 봐보자
회전하기 전, (3,3)이 되고 회전 후에도 (3,3)이 된다.
또 그 바로 아래 빨간 박스의 좌표도 확인 해보자.
회전하기 전, (4,3) 회전 후 (3,2) 가 된다. 이렇게 쭉 모든 박스의 좌표를 구하고 변환 후 좌표 값을 구해보다 보니 여기서 한 가지 일련의 규칙을 찾을 수 있었다.
(2,3) → (3,4)
(3,3) → (3,3)
(4,3) → (3,2)
규칙 1. 회전하기 전 x 값은 회전 후의 Y 값이 된다.
현재 풀이 과정에선 모든 좌표를 계산하는 과정을 올리진 않았지만, 실제로는 진짜 모든 좌표가 어떻게 변환했는지 확인했었고, 다른 테스트 케이스를 혼자 구성해서 확인과 검증을 거친 결과
이 규칙1은 유효했다.
규칙 2. N - Y - 1 = 회전 후 X 값이 된다.
전체 크기 N과 회전하기 전 Y값을 빼봤다. 예를 들어 현재 N이 7이고 회전하기 전 Y 값은 2 이라고
한다면 7 - 2 = 5가 된다. 7 - 3 = 4 , 7 - 4 = 3 … 해당 규칙을 보면 회전 후의 X 값과 1만큼 차이 나는 규칙을 또 확인 할 수 있다.
코드로 구현해보자.
char rotatedMap[MAX][MAX]; void rotate() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { rotatedMap[j][N - 1 - i] = _map[i][j]; } } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { _map[i][j] = rotatedMap[i][j]; } } }