[백준]JAVA - 1028번: 다이아몬드 광산

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

1028번: 다이아몬드 광산

🔶 풀이

처음으로 도전한 플레티넘 문제, 퇴근 후에 하루종일 풀었다...

최근에 풀었던 [가장 큰 정사각형] 문제 상위버전인듯하다.

 

row와 col의 최대 크기는 750, 단순 완전 탐색으로는 시간초과가 발생하기 때문에 dp를 활용해야 함

 

1. map[row][col]에서 값이 1인 경우에 4방향(↙ ↘ ↖ ↗)으로 뻗어나가면서 변의 길이를 구한다.

public static int getSize(int x, int y, int d) {
    int size = 0;
        
    int dx = 0;
    int dy = 0;
        
    while (true) {
        int nx = x + dx;
        int ny = y + dy;
            
        if (d == 0) {        // ↙
            dx++;
            dy--;
        } else if (d == 1) { // ↘
            dx++;
            dy++;
        } else if (d == 2) { // ↖
            dx--;
            dy--;
        } else if (d == 3) { // ↗
            dx--;
            dy++;
        }
            
        // 범위를 벗어나거나 값이 0인 경우
        if (nx < 0 || ny < 0 || nx > N-1 || ny > M-1 || map[nx][ny] == 0) break;
        size++;
    }
        
    return size;
}

 

2. 각 각의 dp에 변의 길이를 넣어줬으면 한 꼭짓점을 기준으로 다이아몬드 모양을 찾아주면 된다.

int maxSize = 0;
for (int i=0; i<N; i++) {
    for (int j=0; j<M; j++) {
        if (map[i][j] == 1) {
            for (int d=0; d<4; d++) {
                dp[i][j][d] = getSize(i, j, d);
            }
                    
            // ↖(2) ↗(3) 변 길이가 maxSize를 넘는 경우 
            if (dp[i][j][2] > maxSize && dp[i][j][3] > maxSize) {
                int len = Math.min(dp[i][j][2], dp[i][j][3])-1;
                        
                // 최대길이부터 maxSize 까지 다이아몬드 모양이 되는지 확인
                for (int tmpLen=len; tmpLen>=maxSize; tmpLen--) {
                    if (i-(2*tmpLen) < 0) continue;
                            
                    // ↙(0) ↘(1) 변 길이가 tmpLen를 넘었을 경우
                    if (dp[i-(2*tmpLen)][j][0] > tmpLen && dp[i-(2*tmpLen)][j][1] > tmpLen) {
                        maxSize = tmpLen+1;
                        break;
                    }
                }
            }
        }
    }
}

필자는 아래 꼭짓점을 기준으로 정했다.

map[row][col] = 1인 경우에 ↖, ↗ 변의 길이를 구해서 두 개의 변 중에서 작은 값은 len 변수에 넣는다.

 

len 값이 정해졌다면 다이아몬드 위 꼭짓점을 기준으로 ↙, ↘ 변의 길이를 구해야 한다.

위 꼭짓점은 row-(2*(len-1)) 이다.

위 그림은 (2,1)을 기준으로 다이아몬드가 그려지는 예제 4번이다.

row: 2 / len: 2 이므로 위 꼭짓점은 (0,1)이 된다.

 

len 값을 구해줄 때, 더 큰 값을 선택하면 다이아몬드 모양이 깨지기 때문에 두 개의 변 중에 작은 값을 선택해 주면 된다.

 

위  꼭짓점을 기준으로 ↙, ↘ 변의 길이를 len 값부터 1씩 내려가면서 구해주면 된다.

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    static int N, M, map[][];
    static int dp[][][];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new int[750][750];   // row, col 최대 범위 : 750
        dp = new int[750][750][4]; // 동, 서, 남, 북 방향 4개
        
        for (int i=0; i<N; i++) {
            String str = br.readLine();
            for (int j=0; j<M; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }          
        
        // 크기가 1x1 일 경우
        if (N == 1 && M == 1) {
            System.out.println(map[0][0]);
            return;
        }
        
        // 최대 다이아몬드 모양 찾기
        int maxSize = 0;
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                if (map[i][j] == 1) {
                    for (int d=0; d<4; d++) {
                        dp[i][j][d] = getSize(i, j, d);
                    }
                    
                    // ↖(2) ↗(3) 변 길이가 maxSize를 넘는 경우 
                    if (dp[i][j][2] > maxSize && dp[i][j][3] > maxSize) {
                        int len = Math.min(dp[i][j][2], dp[i][j][3])-1;
                        
                        // 최대길이부터 maxSize 까지 다이아몬드 모양이 되는지 확인
                        for (int tmpLen=len; tmpLen>=maxSize; tmpLen--) {
                            if (i-(2*tmpLen) < 0) continue;
                            
                            // ↙(0) ↘(1) 변 길이가 tmpLen를 넘었을 경우
                            if (dp[i-(2*tmpLen)][j][0] > tmpLen && dp[i-(2*tmpLen)][j][1] > tmpLen) {
                                maxSize = tmpLen+1;
                                break;
                            }
                        }
                    }
                }
            }
        }        
        
        
        System.out.println(maxSize);
    }
    
    // 0: 위 꼭짓점 기준 왼쪽 아래
    // 1: 위 꼭짓점 기준 오른쪽 아래
    // 2: 아래 꼭짓점 기준 왼쪽 위
    // 3: 아래 꼭짓점 기준 오른쪽 위
    public static int getSize(int x, int y, int d) {
        int size = 0;
        
        int dx = 0;
        int dy = 0;
        
        while (true) {
            int nx = x + dx;
            int ny = y + dy;
            
            if (d == 0) {        // ↙
                dx++;
                dy--;
            } else if (d == 1) { // ↘
                dx++;
                dy++;
            } else if (d == 2) { // ↖
                dx--;
                dy--;
            } else if (d == 3) { // ↗
                dx--;
                dy++;
            }
            
            // 범위를 벗어나거나 값이 0인 경우
            if (nx < 0 || ny < 0 || nx > N-1 || ny > M-1 || map[nx][ny] == 0) break;
            size++;
        }
        
        return size;
    }
}