처음에는 단순구현으로 접근하고 이후 시간을 줄일 수 있는 방법에 대해 고민해봤다.
하지만 이 방법은 해결하지 못하고 다른 분의 아이디어를 얻어 그 방법으로 해결했다.
알고나니 되게 간단하게 느껴지지만 처음 아이디어를 생각할 때는 방법이 전혀 생각나지 않았다.
역시 경험이 중요한듯
제출코드
import sys
input = sys.stdin.readline
R, C = map(int, input().split())
## 패딩 넣는 과정
# rd, ld, ru, lu 값을 만드는 과정에서 경계값 처리를 수월하게 하기 위해
arr = [[0] * (C+2)]
for _ in range(R):
arr.append([0] + list(map(int, input().rstrip())) + [0])
arr += [[0] * (C+2)]
rd = [[0]*(C+2) for _ in range(R+2)] # 오른쪽 아래 방향으로 이어지는 1의 개수
ld = [[0]*(C+2) for _ in range(R+2)] # 왼쪽 아래 방향 ~
ru = [[0]*(C+2) for _ in range(R+2)] # 오른쪽 윗 방향 ~
lu = [[0]*(C+2) for _ in range(R+2)] # 왼쪽 윗 방향 ~
# rd, ld
for i in range(R, 0, -1):
for j in range(1, C+1):
if arr[i][j]:
rd[i][j] = rd[i+1][j+1] + 1
ld[i][j] = ld[i+1][j-1] + 1
# ru, lu
for i in range(1, R+1):
for j in range(1, C+1):
if arr[i][j]:
ru[i][j] = ru[i-1][j+1] + 1
lu[i][j] = lu[i-1][j-1] + 1
ans = 0
for i in range(1, R+1):
for j in range(1, C+1):
for k in range(ans+1, min(ld[i][j], rd[i][j])+1):
bi = i + 2*(k-1)
if bi <= R:
if min(lu[bi][j], ru[bi][j]) >= k:
ans = k
print(ans)접근 방법
주어지는 배열 외에 추가로 4개의 배열을 만든다. 이 배열은 특정 대각선 방향으로 이어지는 1의 개수를 의미한다. 예를 들어 ru[1][2] == 3 이라면 (1, 2) 의 위치에서 오른쪽 윗방향으로 이어지는 1의 개수가 최대 3개까지 이어진다는 의미이다.
이렇게 4개의 배열을 추가적으로 만들고 나면 모든 좌표에서 ld, rd 값을 살펴본다.
(i, j) 에서 ld, rd 값은 ↙ ↘ 방향으로 얼마만큼의 1이 이어지는지 알 수 있다.
그리고 여기서 (i, j) 를 다이아의 위 꼭지점이라고 하면 min(ld[i][j], rd[i][j]) 크기의 다이아가 나올 가능성이 있음을 알 수 있다. "가능성"이다. 뒤에 추가적인 확인이 필요하다.
예를들어 ld[2][3] == 5, rd[2][3] == 3 이라고 하자. 그럼 (2, 3) 을 위 꼭지점으로 하는 다이아는 일단 크기가 3 까지 될 가능성이 있다는 말이된다. 크기 ld 가 길어도 rd 가 그만큼 길지 못하기 때문에 의미가 없다.
다이아를 가로로 잘랐을때 여기까지 상단부를 체크했다. 이제 하단부를 체크할 차례이다.
하단부 체크는 상단부와 똑같다. 그냥 뒤집어서 아래 꼭지점에서 min(lu[i][j], ru[i][j]) 을 확인 할 것이다.
그러기 위해서는 아래 꼭지점 좌표를 구해야 한다. j값(x축 좌표) 는 위 꼭지점과 똑같다. 그리고 i값(y축 좌표) 는 다이아 크기를 알면 구할 수 있다. 크기가 k 인 다이아의 위쪽 꼭지점 좌표가 (a, b) 라면 아래 꼭지점 좌표는 (a+2*(k-1), b) 값으로 구할 수 있다.
아래쪽 좌표를 구했으니 이제 그 좌표에서 lu, ru 값을 체크하자. 크기 k로 구한 아래 꼭지점 좌표에서 lu, ru 값이 모두 k 보다 크다면 크기 k 의 다이아를 만들 수 있다 라는 결론을 내릴 수 있다.
이 방법의 시간복잡도는 O(aRC) 이다. a값에 따라서 시간초과가 될 수 있으니 적절한 가지치기가 필요하다.
참고
