백준 14734번 Aztec Diamond (cpp)

https://www.acmicpc.net/problem/14734

14734번: Aztec Diamond

 

 이 문제는 스페셜 저지이다. 이런 유형의 문제를 풀기 위해서는 순서를 강제해야 해야 한다. 이 문제도 그런지는 모르겠지만. 종만북이 그랬다. 위에 거 회전했다가 아래 거 회전했다가 하면 중복되는 경우도 잡아내기 힘들지 않겠는가?

 이 문제 풀이에 대한 착안은, 블록 하나를 두면 그 블록에 의해서 특정 위치에 특정한 모양으로 존재할 수밖에 없는 경우가 있다는 것에서 시작했다. 이것을 이용해 부분 문제로 쪼갤 수 있다.

 n = 3 일 때 저 위치에 세로 모양으로 블록을 둔다고 가정하면 일부 블록은 반드시 오른쪽 모양처럼 배치되어야 한다. 저 모양들이 배치된 후 남은 공간은 n = 2 일 때와 같다. 즉, 크기가 n 일 때 현재 모양에서 맨 위에 세로 모양의 블록이 배치되었다면 크기가 n - 1 인 문제와 동일한 문제임을 보장할 수 있다.
 현재 풀어야 하는 모양에서 맨 위 블록이 가로로 배치되어 있다면 세로로 회전시켜야 한다. 경우의 수는 다음과 같다.

 우리의 목표는 현재 모양에서 맨 위를 1번과 같은 모양으로 만드는 것이다. 1번 모양을 만들면 크기가 n-1 인 문제로 바뀐다. row 행 column 열 위치의 블록을 세로로 바꿔주는 함수를 dfs(row, column) 이라고 하자.
 2번의 경우 바로 회전시킬 수 있다. 3번의 경우도 한 번 회전시키면 2번 모양으로 바뀐다. 4번에서 왼쪽 아래 모양을 세로로 만들고, 5번에서 오른쪽 아래 모양을 세로로 만들면 3번 모양이 된다. 4번 모양에서 맨 위에 있는 블록을 제거하고 나서 보면 처음 우리가 가졌던 목표와 같음을 알 수 있다. 4번의 경우 dfs(row + 1, column - 1) 로 해결이 가능하다. 5번도 같은 방법으로 해결 가능하다.

헤더는 알아서 준비하시길...

int n;
char grid[205][205];
vector<pair<int, int>> v;

void rotate(int r, int c) {
    v.push_back(make_pair(r+1, c+1));

    if (grid[r][c] == 'L') {
        grid[r][c] = 'U';
        grid[r][c + 1] = 'U';
        grid[r + 1][c] = 'D';
        grid[r + 1][c + 1] = 'D';
    }
    else {
        grid[r][c] = 'L';
        grid[r][c + 1] = 'R';
        grid[r + 1][c] = 'L';
        grid[r + 1][c + 1] = 'R';
    }
}

void dfs(int r, int c) {
    if (grid[r][c] == 'L') {
        // 4번
        if (grid[r + 1][c] == 'R') {
            dfs(r + 1, c - 1);
        }
        // 5번
        if (grid[r + 1][c + 1] == 'L') {
            dfs(r + 1, c + 1);
        }
        // 3번
        if (grid[r + 1][c] == 'U') {
            rotate(r + 1, c);
        }
        // 2번
        rotate(r, c);
    }
}

int main() {
    cin >> n;
    int len = 2 * n;

    for (int i = 0; i < len; ++i) {
        scanf("%s", grid[i]);
    }

    for (int i = 0; i < n; ++i) {
        dfs(i * 2, n - 1);
    }

    cout << v.size() << endl;
    for (int i = 0; i < v.size(); ++i) {
        printf("%d %d\n", v[i].first, v[i].second);
    }

    return 0;
}