문제

다이아몬드 광산은 0과 1로 이루어진 R행* C열 크기의 배열이다.

다이아몬드는 1로 이루어진 정사각형의 경계선을 45도 회전시킨 모양이다. 크기가 1, 2, 3인 다이아몬드 모양은 다음과 같이 생겼다.

다이아몬드 광산에서 가장 큰 다이아몬드의 크기를 출력하는 프로그램을 작성하시오.

size 1:    size 2:    size 3:
                         1
              1         1 1
   1         1 1       1   1
              1         1 1
                         1

입력

첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다.

출력

첫째 줄에 다이아몬드 광산에서 가장 큰 다이아몬드의 크기를 출력한다. 만약 다이아몬드가 없을 때는 0을 출력한다.

7트또 좋은 생각이 났어요. 그만 났으면.

6트 대각선 순회

순회를 가로로 하니까 개수를 세고 dp나 메모를 빠르게 기록하는데 문제가 생긴다.

그리고 지금까지 ↗️방향 정보를 얻으려면 그 방향으로 끝까지 1을 센 후 원위치 돌아와 개수를 기록했는데 1을 세기 위해 탐색한 자리에 아무 정보가 남지 않는다. 이전 탐색 정보를 불러오는 코드를 짰지만 비효율적이다. 해결하려고 하니 점점 코드가 복잡해진다.

1트~5트 까지의 코드와 그림을 살펴보다가 새로운 아이디어가 떠올랐다!

바로 대각선 정보가 중요하니까 대각선으로 2d array를 순회하는 것이다.

대각선으로 가면 마주 보는 두 방향을 한 번에 측정할 수 있을 것 같다.

게다가 대각선 순회를 하면서 셀 때 정보 역방향으로 세어 버리면 최종 몇 개 연속으로 나올지 고민하지 않고 메모리에 1,2,3,4 순차 기록해 버리면 된다. 이 정보를 역방향에서 이용하면 해당 방향의 앞에 1이 몇 개 있는지 알려주는 미래 정보가 된다.

위 그림처럼 하면 4방향 탐색을 2방향으로 줄일 수도 있을 것 같다. 연속 기록이 끝나면 연속 기록 횟수만큼 역방향으로 가면서 개수를 기록해주면 또 검색 횟수를 줄일 수 있다!

1. 대각선으로 순회하는 코드를 만들자.

def sw_topdn(arr):
    h, w = len(arr), len(arr[0])
    for sumid in range(h + w - 1):
        for y in range(h):
            x = sumid - y
            if 0 <= x < w:
                print(arr[y][x],end=' ')        
        print()

def ne_topdn(arr):
    h, w = len(arr), len(arr[0])
    for sumid in range(h + w - 1):
        for y in range(h - 1, -1, -1):
            x = w - 1 - (sumid - y)
            if 0 <= x < w:
                print(arr[y][x],end=' ')
        print()

matrix = [[f"{x}{y}" for x in range(5)] 
          for y in range(7)]

print(*matrix,sep="\\n")

print("# 남서쪽으로 탑다운 순회")
sw_topdn(matrix)
print()
print("# 북동쪽으로 탑다운 순회")
ne_topdn(matrix)

['00','10','20','30','40']
['01','11','21','31','41']
['02','12','22','32','42']
['03','13','23','33','43']
['04','14','24','34','44']
['05','15','25','35','45']
['06','16','26','36','46']
# 남서쪽으로 탑다운 순회
00 
10 01 
20 11 02 
30 21 12 03 
40 31 22 13 04 
41 32 23 14 05 
42 33 24 15 06 
43 34 25 16 
44 35 26 
45 36 
46 
# 북동쪽으로 탑다운 순회
40 
41 30 
42 31 20 
43 32 21 10 
44 33 22 11 00 
45 34 23 12 01 
46 35 24 13 02 
36 25 14 03 
26 15 04 
16 05 
06

2. 정보를 기록하는 코드로 만들어 보았다.

좀 더 빨라질까봐 두 대각선 순회 함수를 합쳤는데… 오버헤드는 줄였는지 몰라도 가독성도 안 좋고 너무 복잡하다….벽에서 카운팅이 안 되는 오류가 있었는데 버그 잡느라 오래 걸렸다… 이렇게 짜면 아무도 못 알아볼 것 같다.

def sw_nw_topdn(arr,h,w,dp): # 남동 북서 방향으로 동시에 2D array순회하는 코드
    sw,se,ne,nw = 0,1,2,3 # 방향을 헷갈릴까봐 숫자 주소 대신 변수명 사용
    for sumid in range(h + w - 1): # 인덱스 합을 늘려가면서 순회
        combo_sw,combo_nw = 0,0 # 1개수 세기 변수 초기화
        for y1 in range(h): 
            x1 = sumid - y1
            if 0 <= x1 < w:
                print(arr[y1][x1],end=' ')
                if arr[y1][x1]==1:
                    combo_sw+=1
                    dp[y1][x1][ne]=combo_sw
                    if 0 == x1 or y1 == h-1:
                        for i in range(combo_sw):
                            dp[y1-i][x1+i][sw]= i+1
                        combo_sw=0
            else:
                if combo_sw>0:
                    for i in range(1,combo_sw+1):
                        dp[y1-i][x1+i][sw]= i
                combo_sw=0
            y2 = h-y1-1
            x2 = w - 1 - (sumid - y2)
            if 0 <= x2 < w:
                print(arr[y2][x2],end=' ')
                if arr[y2][x2]==1:
                    combo_nw+=1
                    dp[y2][x2][se]=combo_nw
                    if 0 == x2 or 0 == y2:
                        for i in range(combo_nw):
                            dp[y2+i][x2+i][nw]= i+1
                        combo_nw=0
            else:
                if combo_nw>0:
                    for i in range(1,combo_nw+1):
                        dp[y2+i][x2+i][nw]= i
                combo_nw=0      
        print()

import random
#matrix = [[f"{10*x+y:02d}" for x in range(5)] for y in range(5)]
matrix = [[1 for x in range(6)] for y in range(6)]
#matrix = [[random.randint(0,1) for x in range(8)] for y in range(23)]
h,w = len(matrix),len(matrix[0])
dp=[[[0,0,0,0] for _ in range(w)] for _ in range(h)]
print(*matrix,sep="\\n")
sw_nw_topdn(matrix,h,w,dp)
print(*dp,sep="\\n")

[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1]

#코드로 생성된 배열의 모습

1 1   # 남동, 북서방향으로 동시에
1 1 1 1   # 배열을 읽어서 생긴 패턴
1 1 1 1 1 1 
1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 
1 1 1 1 1 1 
1 1 1 1 
1 1

[[1, 6, 1, 1], [2, 5, 1, 1], [3, 4, 1, 1], [4, 3, 1, 1], [5, 2, 1, 1], [6, 1, 1, 1]]
[[1, 5, 2, 1], [2, 5, 2, 2], [3, 4, 2, 2], [4, 3, 2, 2], [5, 2, 2, 2], [5, 1, 1, 2]]
[[1, 4, 3, 1], [2, 4, 3, 2], [3, 4, 3, 3], [4, 3, 3, 3], [4, 2, 2, 3], [4, 1, 1, 3]]
[[1, 3, 4, 1], [2, 3, 4, 2], [3, 3, 4, 3], [3, 3, 3, 4], [3, 2, 2, 4], [3, 1, 1, 4]]
[[1, 2, 5, 1], [2, 2, 5, 2], [2, 2, 4, 3], [2, 2, 3, 4], [2, 2, 2, 5], [2, 1, 1, 5]]
[[1, 1, 6, 1], [1, 1, 5, 2], [1, 1, 4, 3], [1, 1, 3, 4], [1, 1, 2, 5], [1, 1, 1, 6]]
##드디어 생성된 dp지도!!