[백준/DP] 1028번 다이아몬드 광산 (JAVA)

문제

---

풀이

1차 시도: 실패

1. 좌표에서 네 방향의 대각선 최대 길이를 각각 구해 dp[i][j][direction]에 저장한다.
2. 좌상단과 우상단 대각선 길이가 모두 1이 넘는 경우,
   • 둘 중 더 작은 값을 대각선 길이 length로 설정하고
   • 좌상단 꼭짓점에서 우상단 대각선 길이가 length 이상인지 확인한다.
   • 우상단 꼭짓점에서 좌상단 대각선 길이가 length 이상인지 확인한다.
   • 만약 두 조건을 모두 만족하면 다이아몬드가 만들어진 것이므로, maxSize를 최댓값으로 갱신한다.

이러한 풀이로 풀었는데, 오답이다. dp답게 이전에 계산해놓은 값을 활용하면서 빈틈없이 로직을 짰다고 생각했는데 반례가 있나보다.. 근데 반례 테스트 케이스를 찾지 못해서 삽질을 꽤 오래하고 있다. 답답하다!

결국 백준 질문 검색에다가 글도 올렸다... 누군가 반례를 안다면 댓글과.. 도움을..ㅠㅠ

import java.io.*;

public class Main {

    private static final int MAXIMUM = 750;

    private static final int DIRECTIONS = 4;
    private static final int LEFT_DOWN = 0;
    private static final int RIGHT_DOWN = 1;
    private static final int LEFT_UP = 2;
    private static final int RIGHT_UP = 3;

    private static int r;
    private static int c;
    private static int maxSize;
    private static int[][] mine = new int[MAXIMUM][MAXIMUM];
    private static int[][][] dp = new int[MAXIMUM][MAXIMUM][DIRECTIONS];

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

        parseInput(br);
        dp();
        bw.append(String.valueOf(maxSize));

        br.close();
        bw.close();
    }

    private static void parseInput(BufferedReader br) throws IOException {
        String[] line = br.readLine().split(" ");
        r = Integer.parseInt(line[0]);
        c = Integer.parseInt(line[1]);

        for (int i = 0; i < r; i++) {
            line = br.readLine().split("");
            for (int j = 0; j < c; j++)
                mine[i][j] = Integer.parseInt(line[j]);
        }
    }

    private static void dp() {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (mine[i][j] == 1) {
                    maxSize = Math.max(maxSize, 1);
                    for (int direction = LEFT_DOWN; direction < DIRECTIONS; direction++)
                        dp[i][j][direction] = countMaxLengthOnDirection(i, j, direction);
                    
                    if (dp[i][j][LEFT_UP] > maxSize && dp[i][j][RIGHT_UP] > maxSize) {
                        int length = Math.min(dp[i][j][LEFT_UP], dp[i][j][RIGHT_UP]);
                        if (dp[i - length + 1][j - length + 1][RIGHT_UP] >= length
                                && dp[i - length + 1][j + length - 1][LEFT_UP] >= length)
                            maxSize = length;
                    }
                }
            }
        }
    }

    private static int countMaxLengthOnDirection(int i, int j, int direction) {
        int count = 0;
        int dy = 0, dx = 0;
        int ny, nx;
        while (true) {
            ny = i + dy;
            nx = j + dx;
            if (!isInBound(ny, nx) || mine[ny][nx] == 0) break;
            count++;

            if (direction == LEFT_DOWN) {
                dy++;
                dx--;
            } else if (direction == RIGHT_DOWN) {
                dy++;
                dx++;
            } else if (direction == LEFT_UP) {
                dy--;
                dx--;
            } else if (direction == RIGHT_UP) {
                dy--;
                dx++;
            }
        }
        return count;
    }

    private static boolean isInBound(int i, int j) {
        return i >= 0 && j >= 0 && i < r && j < c;
    }
}