👨‍💻 문제

---

✍️ 풀이

연속성 측정

배열을 순회하며 행/열 별로 체스판 패턴이 연속적으로 나오는 횟수를 기록한다.

BWBWB  12345
WWWWW  11111
BBWBW  11234
WBBWB  12123
BBWBW  11234

11111
21212
32121
41232
51343

특정 좌표에서의 체스판 최대 크기

만들어둔 배열을 통해 특정 좌표에서의 체스판 최대 크기를 측정할 수 있다.

특정 좌표에서는 해당 좌표를 기준으로 상단, 좌측의 연속성을 판단할 수 있다.
좌표를 상단좌측(대각선)으로 한 칸씩 이동하면서 정사각형 형태의 체스판의 최대 크기를 측정할 수 있다.

예시: (4, 4)

....B  .....
....W  .....
....W  .....
....B  .....
BBWBW  ....4

.....
.....
.....
.....
....3

가로/세로의 연속성 중 작은 수치가 최대 크기

현재 가능한 최대 크기 : 3

...W.  .....
...W.  .....
...B.  .....
WBBW.  ...2.
.....  .....

.....
.....
.....
...3.
.....

대각선으로 한 칸 거슬러 올라갔기 때문에 크기 수치 1 증가
(4, 4)가 'W'이었기 때문에 (3, 3)도 'W'이어야 함

현재 가능한 최대 크기 : 2 + 1

..B..  .....
..W..  .....
BBW..  ..2..
.....  .....
.....  .....

.....
.....
..1..
.....
.....

대각선으로 두 칸 거슬러 올라갔기 때문에 크기 수치 2 증가
(2, 2)도 'W'이어야 함

현재 가능한 최대 크기 : 1 + 2

가로/세로의 연속성 중 작은 수치가 1이기 때문에 더 이상 거슬러 올라가지 않음

이렇게 해당 좌표의 정사각형 최대 크기는 3이 된다.
이는 곧 해당 좌표가 우측하단 꼭짓점이 되는 정사각형이 3개가 생길 수 있음을 의미한다.
결과값이 3만큼 증가하게 된다.

DP

물론 이런 식으로 항상 거슬러 올라가며 계산한다면 이미 했던 계산도 계속하게 되고 느려질 것이다.
새로운 배열을 두어 해당 좌표에서의 최대 크기를 기록한다.
굳이 연달아 거슬러가지 않아도 바로 이전 좌측 상단 기록만을 참고하면 된다.

우측하단에서 좌측상단으로 거슬러올라가며 연산하기 때문에
해당 기록 배열은 좌측상단에서 우측하단으로 기록해나간다.

결과

각 좌표마다의 최대 정사각형 수를 모두 합한 게 결과값이 된다.

---

📄 전체 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    private static int R, C;
    private static String[] board;
    private static int[][] arrV;
    private static int[][] arrH;
    private static int[][] maxSize;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        board = new String[R];
        for (int r=0; r<R; r++) {
            board[r] = br.readLine();
        }

        // 가로 연속성
        arrH = new int[R][C];
        for (int r=0; r<R; r++) {
            arrH[r][0] = 1;
            for (int c=1; c<C; c++) {
                arrH[r][c] = 1;
                if (board[r].charAt(c) != board[r].charAt(c-1)) {
                    arrH[r][c] += arrH[r][c-1];
                }
            }
        }

        // 세로 연속성
        arrV = new int[R][C];
        for (int c=0; c<C; c++) {
            arrV[0][c] = 1;
            for (int r=1; r<R; r++) {
                arrV[r][c] = 1;
                if (board[r].charAt(c) != board[r-1].charAt(c)) {
                    arrV[r][c] += arrV[r-1][c];
                }
            }
        }

        // 측정
        long result = 0;
        maxSize = new int[R][C];
        for (int r=0; r<R; r++) {
            for (int c=0; c<C; c++) {
                maxSize[r][c] = Math.min(arrH[r][c], arrV[r][c]);
                if (r>0 && c>0) {
                    if (board[r].charAt(c) != board[r-1].charAt(c-1)) {
                        // 좌측상단 칸이 다른 값이면 이전 최대 크기를 생각하지 않음
                        maxSize[r][c] = 1;
                    }
                    else {
                        maxSize[r][c] = Math.min(maxSize[r][c], maxSize[r-1][c-1] + 1);
                    }
                }
                result += maxSize[r][c];
            }
        }
        System.out.println(result);

    }

}

---