Diamond Mining(Dynamic Programming, Graph)

http://topcoder.bgcoder.com/print.php?id=2390

TopCoder problem "DiamondMining" used in TCHS09 Round 3 (Division I Level Three)

TopCoder problem "DiamondMining" used in TCHS09 Round 3 (Division I Level Three)

Problem Statement
	A diamond mine is a matrix of ones and zeroes with R rows and C columns. A diamond is a pattern of ones forming the boundary of a 45-degree rotated square. The diamonds of size 1, 2, and 3 are shown below. The diamond mine in this problem will be pseudo-randomly generated using the following method: You are given two ints: seed and threshold. Let x0=seed and for all i>=0 let xi+1 = (xi * 25173 + 13849) modulo 65536. Process the cells of the matrix in row major order (i.e., first row left to right, second row left to right, etc.). Each time you process a cell, look at the next xi (starting with x1 for the upper left corner). If it is greater than or equal to threshold, the current cell will contain a 1, otherwise it will contain a 0. Your method shall compute and return the size of the largest diamond that can be found in the mine. If there are no diamonds, return 0.
Definition
	Class: DiamondMining Method: largestDiamond Parameters: int, int, int, int Returns: int Method signature: int largestDiamond(int R, int C, int seed, int threshold) (be sure your method is public)
Notes
-	The random generation of the input is only for keeping the input size small. The author's solution does not depend on any properties of the generator, and would work fast enough for any input of allowed dimensions.
Constraints
-	R will be between 1 and 750, inclusive.
-	C will be between 1 and 750, inclusive.
-	seed will be between 0 and 65,535, inclusive.
-	threshold will be between 0 and 65,536, inclusive.

 

문제의 내용은 위와 같지만, 좀 변형해서

 

주어진 list[list[int]] graph에 대해서 포함하고 있는 가장 큰 다이아몬드의 크기를 구하는 것이다.

 

다이아몬드는 우리가 흔히 하는 다이아몬드 모양이 '1'로만 이루어진 체로 얼마나 연속적으로 자리하고 있는 지를 보는 것

 

아래 test case를 참고하면 더 잘 알 수 있다.

 

우여곡절 끝에 풀었다.

 

사실 이 문제는 category는 Dynamic Programming인데, 그게 의미가 있나 싶어서.. Naive하게 풀어냈다.

while문 for문이 덕지 덕지 붙어 있어서 좀 더럽긴 한데 이 외에 효율적인 코드가 생각이 안 난다.

 

일단 요지는 전체 mine data를 돌다가 1을 발견하면 그 1로부터 좌하단 우하단을 scan하며 1을 count 한다.

그러면 다이아몬드에서 위아래 반띵 했을 때 윗부분에 대해서 먼저 검토를 할 수 있다.

 

계산결과로 윗부분에서 다이아몬드를 이룰 수 있는 Minimum 변의 길이를 알 수 있다.

 

어차피 윗 부분도 좌우 변의 길이는 대칭이 되어야 하기떄문에 min값만 고려하면 된다.

 

그 min 값 기준으로 이번엔 다이아몬드의 아랫부분을 검증하는 것이다.

 

min 값 기준으로 윗퉁에서 좌하단으로 검토하던 변은 우하단으로 1이 있는지 꺾어서 Check하고,

 

윗통에서 우하단으로 1을 검토하던 변은 좌하단으로 1이 있는지 꺾어서 Check 하면 다이아몬드가 형성되는지 알 수 있다.

 

이 때도 while문을 겹쳐서 써서 밑 둥에서도 Minimum '1'로 이루어진 변의 길이를 탐색해서 다이아몬드의 크기를 추출한다.

 

말이 좀 이해가 안 갈 수 있는데, 코드를 보다보면 대충 무슨 느낌인 지 알 것이다.

 

다만 얼핏봐도 Time complexity가 엄청날 거 같은데, 뭐 어쩌겠나.. 이런 문제는 그냥 맨땅에 해딩하는 심정으로 푸는 거라서 시간효율을 따지진 못했다 ㅠ

 

def problem3(mine: list[list[int]]) -> int:
    if not mine or not mine[0]:
        return 0
    n, m = len(mine), len(mine[0]) # 사실 m = n 이다 input이 Square 이라서
    ans = 0
    # 다이아몬드 크기 계산 함수
    def diamond_size(x, y):
        cnt1, cnt2 = 0, 0
        i, j = x, y
        # 대각선 d1 (↘)
        while i < m and j < n and mine[i][j] == 1:
            cnt1 += 1
            i += 1
            j += 1
        # 대각선 d2 (↙)
        i, j = x, y
        while i < m and 0 <= j and mine[i][j] == 1:
            cnt2 += 1
            i += 1
            j -= 1
        # 아래대칭 구조도 검증해서 다이아몬드 모양 맞는지 확인
        temp = min(cnt1, cnt2)
        while temp != 1 :
            i1, j1 = x + (temp-1), y - (temp-1)
            i2, j2 = x + (temp-1), y + (temp-1)
            cnt = 0
            while cnt != temp:
                if  i1 < n and i2 < n and j1 < n and j2 >= 0 and mine[i1][j1] == 1 and mine[i2][j2] == 1 :
                    i1 += 1
                    j1 += 1
                    i2 += 1
                    j2 -= 1
                    cnt +=1 
                else : break
            if cnt == temp : return cnt
            else : temp -= 1
        return temp
    # 전체 탐색
    for i in range(n):
        for j in range(m):
            if mine[i][j] == 1:
                # 현재 위치를 중심으로 다이아몬드 크기를 계산
                ans = max(ans, diamond_size(i, j))
    
    return ans
    # Test your code
print(problem3([[0,1,1,0,0],
                [0,1,0,1,1],
                [1,1,1,1,1],
                [0,1,1,1,1],
                [1,1,1,1,1]])
                )#3
print(problem3([[0]])
                )#0
print(problem3([[1]])
                )#1
print(problem3([[0,1,0],
                [1,0,1],
                [0,1,0]])
                )#2
print(problem3([[0,0,0,0,0],
                [0,0,0,0,0],
                [1,0,1,0,1],
                [0,1,0,1,1],
                [1,0,0,0,1]])
                )#1
print(problem3([[0,0,1,0,0],
                [0,1,1,1,0],
                [1,0,1,0,1],
                [0,0,0,0,0],
                [1,0,1,0,1]])
                )#2
print(problem3([[1,1,1,1,1,1],
                [0,1,1,1,0,1],
                [1,0,1,0,1,1],
                [0,1,0,0,0,1],
                [1,0,1,0,1,1],
                [1,0,1,1,1,1]])
                )#3

 

솔직히 

    up_right = [[0] * m for _ in range(n)]  # ↗
    up_left = [[0] * m for _ in range(n)]   # ↖
    down_right = [[0] * m for _ in range(n)]  # ↘
    down_left = [[0] * m for _ in range(n)]   # ↙

 

이런식으로 DP를 짜서 풀면 더 빨리 풀 수 있을 거 같은데,

 

내 머리속엔 떠오르지가 않는다..