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

문제 링크

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

사용 알고리즘

• DP
• 누적 합

풀이

주어진 배열 안에서 나타나는 가장 큰 다이아몬드 모양의 크기를 구하는 문제이다.

 

첫 시도에는 주어진 행, 열의 크기에 따라 나타날 수 있는 모든 다이아몬드 모양의 좌표를 저장해두고 각 모양마다 해당 모양을 만족하는 경우가 있는지 확인하는 식으로 구현했지만 시간 초과가 발생해서 다른 사람의 풀이를 보고 해결했다.

---

이 문제를 풀기 위해서는 다이아몬드의 성질을 파악해야 한다.

 

특정 좌표를 다이아몬드 모양의 가장 왼쪽 좌표가 `(y, x)`라고 가정했을 경우,

`(y, x)`에서부터 우측 상단, 우측 하단으로 연속된 1의 개수와

`(y, x + 2 * (size - 1))`좌표에서의 좌측 상단, 좌측 하단으로 연속된 1의 개수가 size 보다 크다면 해당 크기의 다이아몬드 모양을 만들 수 있다.

예제

입력

5 5
01100
01011
11111
01111
11111

 

출력

3

 

 

아래 사진과 같은 입력이 주어질 경우, 이 중 가장 큰 크기의 다이아몬드 모양은 다이아몬드 모양의 가장 왼쪽 좌표가 (2, 0)인 크기 3인 다이아몬드이다.

 

이를 구하기 위해 각 좌표에서 우측 상단, 우측 하단, 좌측 상단, 좌측 하단으로 연속된 1의 개수를 카운팅해주자.

이 때, DP를 이용하면 보다 빠른 속도로 연속된 1의 개수를 구할 수 있다.

 

(0, 0)부터 탐색을 진행한다고 가정하고, 현재 좌표가 (2, 0)일 경우를 보자.

(2, 0)에서 만들 수 있는 다이아몬드의 최대 크기는 `우측 상단, 우측 하단 중 최소값 = 3`이므로 크기가 3인 다이아몬드를 만들 수 있는지 확인해보자.

 

다이아몬드를 만들기 위해선 다이아몬드의 가장 우측 좌표에서 각각 좌측 상단, 좌측 하단으로 뻗어나가는 크기가 3보다 크거나 같아야 한다.

다이아몬드의 가장 좌측 좌표가 (2, 0)이고 크기가 3이므로 다이아몬드의 가장 우측 좌표는 `(2, 0 + 2 * (3 - 1)) = (2, 4)`이 된다.

(2, 4) 좌표에서 좌측 상단, 좌측 하단으로 연속되어 있는 1의 수가 각각 3, 3이기 때문에 이를 만족한다.

이 순서대로 반복하면 가장 큰 다이아몬드 모양의 크기를 구할 수 있다.

코드

import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

n, m = map(int, input().split())
arr = [input() for _ in range(n)]

ul = [[0] * m for _ in range(n)]
ur = [[0] * m for _ in range(n)]
dl = [[0] * m for _ in range(n)]
dr = [[0] * m for _ in range(n)]

for y in range(n):
    for x in range(m):
        if arr[y][x] != '1': continue

        ul[y][x] = (ul[y - 1][x - 1] + 1) if y > 0 and x > 0 else 1
        ur[y][x] = (ur[y - 1][x + 1] + 1) if y > 0 and x < m - 1 else 1

for y in range(n - 1, -1, -1):
    for x in range(m - 1, -1, -1):
        if arr[y][x] != '1': continue

        dl[y][x] = (dl[y + 1][x - 1] + 1) if y < n - 1 and x > 0 else 1
        dr[y][x] = (dr[y + 1][x + 1] + 1) if y < n - 1 and x < m - 1 else 1

res = 0
for y in range(n):
    for x in range(m):
        limit = min(ur[y][x], dr[y][x])
        for size in range(limit, res, -1):
            ny, nx = y, x + 2 * (size - 1)
            if nx >= m: continue
            if ul[ny][nx] >= size and dl[ny][nx] >= size:
                res = max(res, size)
                break

print(res)