취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 23000번 문제인 L Shaped Plots이다.
문제는 아래 링크를 확인하자.

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

문제에서 찾아야하는 L모양은 (1) 어떠한 교차점이 있으며, (2) 그 교차점에서 2 이상의 \(k\)에 대해 수직으로 \(k\)칸 및 \(2k\)칸이 뻗은 모양으로 생각할 수 있다. 이와 같이 생각하면 해당 모양은 각 칸에서 수직으로 뻗어나갈 두 방향을 고르는 방법 네 가지와 어느 방향으로 더 많은 칸을 연결할지의 두 가지의 곱 8가지 경우를 살피는 것으로 모든 경우의 수를 고려할 수 있음을 알 수 있다.

다만, 모든 L모양 상태에 직접 접근하기에는 경우의 수가 너무 많아질 수 있으므로, 각 칸에 대하여 상하좌우방향으로 이을 수 있는 칸의 개수의 최댓값을 미리 전처리해두자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;

int R, C;
int A[1002][1002];
int sR[1002][1002];
int sL[1002][1002];
int sU[1002][1002];
int sD[1002][1002];

void solve() {
    memset(sR, 0, sizeof(sR));
    memset(sL, 0, sizeof(sL));
    memset(sU, 0, sizeof(sU));
    memset(sD, 0, sizeof(sD));
    ll ans = 0;
    cin >> R >> C;
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            cin >> A[r][c];
        }
    }

    for (int r = 1; r <= R; r++) {
        for (int c = C; c > 0; c--) {
            if (A[r][c]) sR[r][c] = sR[r][c + 1] + 1;
        }
    }
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            if (A[r][c]) sL[r][c] = sL[r][c - 1] + 1;
        }
    }
    for (int c = 1; c <= C; c++) {
        for (int r = R; r > 0; r--) {
            if (A[r][c]) sD[r][c] = sD[r + 1][c] + 1;
        }
    }
    for (int c = 1; c <= C; c++) {
        for (int r = 1; r <= R; r++) {
            if (A[r][c]) sU[r][c] = sU[r - 1][c] + 1;
        }
    }

    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            ans += max(min(sU[r][c] / 2, sR[r][c]) - 1, 0);
            ans += max(min(sU[r][c], sR[r][c] / 2) - 1, 0);
            ans += max(min(sR[r][c] / 2, sD[r][c]) - 1, 0);
            ans += max(min(sR[r][c], sD[r][c] / 2) - 1, 0);
            ans += max(min(sD[r][c] / 2, sL[r][c]) - 1, 0);
            ans += max(min(sD[r][c], sL[r][c] / 2) - 1, 0);
            ans += max(min(sL[r][c] / 2, sU[r][c]) - 1, 0);
            ans += max(min(sL[r][c], sU[r][c] / 2) - 1, 0);
        }
    }

    cout << ans << '\n';
}

int T;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> T;
    for (int t = 1; t <= T; t++) {
        cout << "Case #" << t << ": ";
        solve();
    }
}

BOJ Random Defense #11