다이아몬드 광산

#BOJ1028
다이아까지 영차영차 가기에는 실력이 많이 모자르다는 생각이 많이 들어서 최근 골드 문제로 내실 다지기를 많이 하고 있다. 그러다가 누군가 푼 플레 문제를 훑어 보던 중 대충 풀이에 대한 아이디어가 떠올라서 점수나 올릴 겸 플레 문제를 풀었다. 그나저나 요즘 랩실 갈 준비를 하는데 생각보다 빡센거 같아서 고민이 많이 된다. 주석은 감사하신 나의 새로운 신 클로드3-opus님께서 해주셨다.

import sys

# 입력받은 행과 열 값을 저장
r, c = map(int, sys.stdin.readline().split())

# 왼쪽 위에서 오른쪽 아래로 가는 대각선의 연속된 1의 개수를 저장할 2차원 리스트 초기화
ld = [[0] * c for _ in range(r)]

# 오른쪽 위에서 왼쪽 아래로 가는 대각선의 연속된 1의 개수를 저장할 2차원 리스트 초기화
rd = [[0] * c for _ in range(r)]

# 입력받은 다이아몬드 모양의 글자를 순회하며 1인 경우 ld와 rd의 해당 위치에 1을 저장
for i in range(r):
    diamond = sys.stdin.readline().strip()
    for j in range(c):
        temp = diamond
        if diamond[j] == '0':
            ld[i][j] = 0
            rd[i][j] = 0
        else:
            ld[i][j] = 1
            rd[i][j] = 1

# 대각선의 연속된 1의 개수를 계산
for i in range(r - 2, -1, -1):
    for j in range(c):
        # 왼쪽 위에서 오른쪽 아래로 가는 대각선의 연속된 1의 개수 계산
        if ld[i][j] == 1 and j != 0:
            ld[i][j] += ld[i + 1][j - 1]
        # 오른쪽 위에서 왼쪽 아래로 가는 대각선의 연속된 1의 개수 계산
        if rd[i][j] == 1 and j != c - 1:
            rd[i][j] += rd[i + 1][j + 1]

# 최대 다이아몬드의 크기를 저장할 변수 초기화
res = 0

# 모든 위치에서 가능한 다이아몬드의 크기를 계산하여 최대 크기 갱신
for i in range(r):
    for j in range(c):
        if ld[i][j] != 0 and rd[i][j] != 0:
            res = max(res, 1)
        if ld[i][j] != 1 and rd[i][j] != 1:
            n = min(ld[i][j], rd[i][j])
            while n > 1:
                if rd[i + n - 1][j - n + 1] >= n and ld[i + n - 1][j + n - 1] >= n:
                    res = max(res, n)
                n -= 1

# 최대 다이아몬드의 크기 출력
print(res)