[DIAMOND] 다이아몬드

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/DIAMOND

algospot.com :: DIAMOND

 

풀이입니다. 🤔

 

import java.util.*;
 
public class Main {
    private static final char SHARP = '#';
    private static final char[][] board = new char[50][50];
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            int h = scanner.nextInt(), w = 0;
            for (int i = 0; i < h; ++i) {
                String line = scanner.next();
                w = line.length();
                for (int j = 0; j < w; ++j) {
                    board[i][j] = line.charAt(j);
                }
            }
 
            int ret = 0;
            for (int i = 0; i < h; ++i) {
                for (int j = 0; j < w; ++j) {
                    ret = Math.max(ret, getMaxDiamondLength(i, j, h, w));
                }
            }
 
            System.out.println(ret);
        }
    }
 
    private static int getMaxDiamondLength(int y, int x, int h, int w) {
        int ret = 0, safety = 0;
        for (int goal = 1; goal <= h; goal += 2) {
            int center = goal / 2;
            for (int distance = safety; distance < goal; ++distance) {
                if (y + distance >= h
                        || !hasLine(y + distance, x, w, (distance > center) ? goal - distance - 1 : distance)) {
                    return ret;
                }
            }
 
            ret = goal;
            safety = center; // 다이아몬드가 있는 것이 증명되었다면, 다음 회차에서 Center 까지는 정확한 # 이 존재함을 보장한다.
        }
        return ret;
    }
 
    private static boolean hasLine(int y, int x, int w, int distance) {
        int startX = x - distance, endX = x + distance;
        if (startX < 0) return false;
        if (endX >= w) return false;
 
        for (int i = startX; i <= endX; ++i) if (board[y][i] != SHARP) return false;
        return true;
    }
}

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️