[NYPC 2016_본선문제] '돌리고 밀고' 문제 풀이

돌리고 밀고

가상의 퍼즐게임에 들어갈 코드를 만들어 보자. 이 퍼즐게임의 게임판은 N×N의 크기이고, 게임판의 각각의 칸은 빈칸이거나, 특정 색의 1×11×1 크기인 정사각형 블럭이 놓여 있다.

이것이 게임판의 초기 상태이다. 이 게임판을 오른쪽으로 90도 돌리면 아래와 같은 모양이 될 것이다.

이 블럭들을 모두 아래쪽으로 끝까지 밀어놓으면 아래와 같은 모양이 된다.

'게임판을 오른쪽으로 90도 회전한 뒤, 블럭들을 모두 아래쪽으로 끝까지 미는' 동작을 SpinAndSlide 라고 정의하자. 주어진 게임판에 SpinAndSlide를 여러번 적용했을 때 그 결과가 어떻게 될지를 알아내 보자.

예를 들어, 바로 위 그림에 SpinAndSlide를 한 번 더 적용한 결과는 아래와 같다.

입력

첫번째 줄에 게임판의 크기를 나타내는 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..

확실히 전등 켜기 문제를 풀고 나니 이런 맵 문제에 대한 거부감이 조금 사라졌다!!
전등 켜기를 일주일간 붙잡고 있었는데 이번 문제는 하루도 안 걸렸다. ㄷㄷ

일단 돌리는 `Spin`부터 실행했는데, 돌리기 전의 여백과 돌리고 난 뒤의 여백을 계산하는 것처럼 규칙을 찾고 나니 문제가 너무 쉬워졌다. `Spin`을 끝내니 오히려 `Slide`가 약간 난해하게 느껴졌는데 그냥 아래로 미는 느낌으로, 그리고 행보다 열을 기준으로 2중 for문의 바깥을 구현해주었더니, 내가 원하는 대로 열을 기준으로 for을 돌릴 수 있게 되었다.

약간 아쉬운 점은 for문을 너무 많이 쓴다는 점이었는데 이건 어쩔 수 없나?,,, 흠.
아무리 생각해도 잘 모르겠다. 아무래도 map이다보니 for문을 많이 쓰는 건 어쩔 수 없는 거 같다.

#include <iostream>
using namespace std;
int N, M; // N = 게임판의 크기, M = Spin and Slide 횟수 
char map[100][100];

void SpinAndSlide() {
    char spin[100][100];
    for (int i = 0; i < N; i++) { // 행
        for (int j = 0; j < N; j++) { // 열
            spin[j][(N - 1) - i] = map[i][j];
        }
    }
    for (int j = N - 1; j >= 0; j--) { // 열 
        int index = N - 1;
        for (int i = N - 1; i >= 0; i--) { // 행
            while (true) {
                if (spin[index][j] == '.') index--;
                else break;
            }
            if (index < 0) map[i][j] = '.';
            else map[i][j] = spin[index--][j];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < str.length(); j++) {
            map[i][j] = str[j];
        }
    }
    for (int i = 0; i < M; i++) {
        SpinAndSlide();
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << map[i][j];
        }
        cout << '\n';
    }
}

각 열과 행의 남는 칸을 확인했다.
예를 들어, (1, 6)의 'A'는 `Spin` 후 (0, 1)이 된다. (여기서 행 열이 헷갈릴 테지만, 해당 좌표는 (x, y), 즉, (열, 행)인 것이다.)
위의 `Spin`한 배열은 spin을 새로 생성해 저장한다.

spin 행 = map의 열
spin 열 = 게임판의 최대 인덱스(게임판 크기 - 1) - map의 행

↑ 원래 게임판, (SpinAndSlide, 1), (SpinAndSlide, 2)

for문을 열부터 돌려 열을 기준으로 2중 for문이 돌아가게끔 했다.
`Slide` 함수는 게임판의 블럭을 아래로 미는 함수기 때문이다.
가장 밑에서부터 탐색하여, spin의 행, 열이 '.'이면 index--;을 해준다. 블럭일 때만 아래로 밀어주면 되기 때문이다.
index가 0 미만일 때는 '.'을 저장한다. 이미 모든 행을 다 보았다는 뜻이기 때문이다.