[백준/Java] 1028 : 다이아몬드 광산

류태호·2026년 4월 25일

Java 다이나믹프로그래밍 백준 알고리즘

백준 풀이

목록 보기

25/26

📌 문제 정보

번호: 1028
제목: 다이아몬드 광산
난이도: Platinum 5
분류: 다이나믹 프로그래밍

📝 문제 요약

R×C 격자(0/1)에서 1로 이루어진 마름모(다이아몬드) 경계 중 가장 큰 크기 찾기. 크기 k 마름모는 가로 폭 (2k−1), 세로 높이 (2k−1)의 속이 빈 마름모

💡 접근 방식

각 칸에서 4방향(↖ ↗ ↙ ↘)으로 연속한 1의 길이를 미리 계산해두면, 마름모의 4변 검사가 O(1)로 끝남. 위 꼭짓점을 기준으로 가능한 가장 큰 k부터 내림차순 시도하고 현재 답보다 작아지면 컷

🔹 1단계 – 4방향 대각선 누적합

각 셀에서 대각선 방향으로 1이 몇 칸 연속하는지 미리 계산

변수	방향	점화식	순회 순서
`lu`	↖	`lu[i-1][j-1] + 1`	위→아래, 왼→오
`ru`	↗	`ru[i-1][j+1] + 1`	위→아래, 오→왼
`ld`	↙	`ld[i+1][j-1] + 1`	아래→위, 왼→오
`rd`	↘	`rd[i+1][j+1] + 1`	아래→위, 오→왼

g[i][j] == 0이면 모두 0으로 초기화

+2 패딩 트릭

int[R+2][C+2] 로 격자를 둘러싸고 실제 데이터를 (1, 1) ~ (R, C)에 저장. 패딩 셀이 자동 0이 되어 i-1, j-1 같은 경계 참조 시 별도 분기 없이 동작

🔹 2단계 – 마름모 4변 검사

위 꼭짓점 (r, c), 크기 k의 마름모는

       (r, c)              ← 위 꼭짓점
       ↙   ↘
    ld     rd 변
       ↘   ↙
   (bottomRow, c)         ← 아래 꼭짓점, bottomRow = r + 2(k-1)
       ↖   ↗
    lu     ru 변

4변 모두 길이 k 이상이면 마름모 존재

위쪽 두 변: ld[r][c] ≥ k && rd[r][c] ≥ k
아래쪽 두 변: lu[bottomRow][c] ≥ k && ru[bottomRow][c] ≥ k

왜 2(k−1)?

크기 k 마름모는 위 꼭짓점 → 중심까지 (k−1) 칸, 중심 → 아래 꼭짓점까지 (k−1) 칸. 합쳐서 위에서 아래까지 행 거리는 2(k−1)

k=3 예시:
row r:      .       ← 위 꼭짓점
row r+1:   . .
row r+2:  .   .     ← 중심
row r+3:   . .
row r+4:    .       ← 아래 꼭짓점 (r에서 4칸 = 2(k-1))

🔹 3단계 – 위 꼭짓점 순회 + 큰 k부터 내림차순

각 (r, c)를 위 꼭짓점 후보로

maxKtop = min(ld[r][c], rd[r][c])     ← 위쪽 두 변으로 가능한 최대 k
for k = maxKtop; k > ans; k--:
    bottomRow = r + 2(k-1)
    if bottomRow > R: continue        ← 격자 밖이면 skip
    if lu[bottomRow][c] >= k && ru[bottomRow][c] >= k:
        ans = k; break                ← 큰 k부터 내려왔으니 첫 성공이 곧 최댓값

핵심 가지치기: k > ans 조건으로 현재 답 이하의 k는 아예 시도 안 함. 이 가지치기가 750×750 시간 제한 통과의 결정적 요인

💻 핵심 코드

// 4방향 대각선 누적합
for (int i = 1; i <= R; i++)
    for (int j = 1; j <= C; j++)
        lu[i][j] = g[i][j] == 1 ? lu[i - 1][j - 1] + 1 : 0;

for (int i = 1; i <= R; i++)
    for (int j = C; j >= 1; j--)
        ru[i][j] = g[i][j] == 1 ? ru[i - 1][j + 1] + 1 : 0;

for (int i = R; i >= 1; i--)
    for (int j = 1; j <= C; j++)
        ld[i][j] = g[i][j] == 1 ? ld[i + 1][j - 1] + 1 : 0;

for (int i = R; i >= 1; i--)
    for (int j = C; j >= 1; j--)
        rd[i][j] = g[i][j] == 1 ? rd[i + 1][j + 1] + 1 : 0;

int ans = 0;
for (int r = 1; r <= R; r++) {
    for (int c = 1; c <= C; c++) {
        int maxKtop = Math.min(ld[r][c], rd[r][c]);
        for (int k = maxKtop; k > ans; k--) {
            int bottomRow = r + 2 * (k - 1);
            if (bottomRow > R) continue;
            if (lu[bottomRow][c] >= k && ru[bottomRow][c] >= k) {
                ans = k;
                break;
            }
        }
    }
}

⏳ 복잡도 분석

시간 복잡도: O(R × C × min(R, C))
- 누적합 전처리는 O(R×C), 마름모 검사는 각 셀에서 최대 min(R,C)/2 번의 k 시도
- 최악 750³ ≈ 4억이지만 k > ans 가지치기로 실제로는 훨씬 적음
공간 복잡도: O(R × C)
- 4개의 (R+2)×(C+2) DP 배열

⚠️ 어려웠던 점

매번 변을 직접 세면 시간 초과라 4방향 누적합을 미리 계산했습니다.
배열 기본 크기로 하다가 경계 검사가 귀찮아서 배열 크게 늘려서 했습니다.

📄 전체 코드

package rtaeho.week04.B1028;

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        int[][] g = new int[R + 2][C + 2];
        for (int i = 1; i <= R; i++) {
            String line = br.readLine();
            for (int j = 1; j <= C; j++) {
                g[i][j] = line.charAt(j - 1) - '0';
            }
        }

        int[][] lu = new int[R + 2][C + 2]; // 왼쪽위
        int[][] ru = new int[R + 2][C + 2]; // 오른쪽위
        int[][] ld = new int[R + 2][C + 2]; // 왼쪽아래
        int[][] rd = new int[R + 2][C + 2]; // 오른쪽아래

        // 왼쪽위
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                lu[i][j] = g[i][j] == 1 ? lu[i - 1][j - 1] + 1 : 0;
            }
        }
        // 오른쪽위
        for (int i = 1; i <= R; i++) {
            for (int j = C; j >= 1; j--) {
                ru[i][j] = g[i][j] == 1 ? ru[i - 1][j + 1] + 1 : 0;
            }
        }

        // 왼쪽아래
        for (int i = R; i >= 1; i--) {
            for (int j = 1; j <= C; j++) {
                ld[i][j] = g[i][j] == 1 ? ld[i + 1][j - 1] + 1 : 0;
            }
        }

        // 오른쪽아래
        for (int i = R; i >= 1; i--) {
            for (int j = C; j >= 1; j--) {
                rd[i][j] = g[i][j] == 1 ? rd[i + 1][j + 1] + 1 : 0;
            }
        }

        int ans = 0;

        for (int r = 1; r <= R; r++) {
            for (int c = 1; c <= C; c++) {
                // 왼쪽아래와 오른쪽아래 중에 작은 값을 기준으로 진행
                int maxKtop = Math.min(ld[r][c], rd[r][c]);
                for (int k = maxKtop; k > ans; k--) {
                    int bottomRow = r + 2 * (k - 1);
                    if (bottomRow > R) {
                        continue;
                    }
                    if (lu[bottomRow][c] >= k && ru[bottomRow][c] >= k) {
                        ans = k;
                        break;
                    }
                }
            }
        }

        System.out.println(ans);
    }
}