Programmers / 가장 큰 사각형 찾기 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 가장 큰 사각형 찾기 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12905

프로그래머스

문제 설명

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

예를 들어

1234

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 있다면 가장 큰 정사각형은

1234

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

제한사항

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

---

입출력 예boardanswer

[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]	9
[[0,0,1,1],[1,1,1,1]]	4

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.

입출력 예 #2
| 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

---

나의 풀이

간단하게 3X3으로 먼저 예시를 들어보겠다.

 

여기에 임의의 숫자를 넣어주자

 

 

그럼 행렬 연산에 있어서 가장자리의 행과 열은 행렬 내부의 규칙과는 다르게 작용할 것이다.

따라서 열이나 행의 인덱스가 0일때는 그냥 넘어간다.

그리고, 해당 칸의 원소가 0일경우도 그냥 넘어간다.

 

# board[i][j] 로 보드를 나타낸다.
for i in range(len(board)):
	for j in range(len(board[i])):
		if i == 0 or j == 0 or board[i][j] == 0:
        	pass

그럼 if문을 통과할 수 있는 첫번째 칸은

동그라미친 해당 원소일 것이다.

그러면 이 원소를 시작으로 가장 큰 정사각형을 만들 수 있는지 확인 하면 된다.

 

해당 부분을 검사하는 코드를 작성한다.

 

여기서 부분적으로 보았을 때 0이라는 원소가 있어서 아직까지 가장 큰 사각형을 만들 수 있진 않다.

그렇다면 가장 작은 원소의 크기를 확인해서 해당 영역에서 0이 있는지 없는지 확인하면 된다.

하지만 다른 영역은 모두 원소를 1로 가질 수 있기 때문에 다음 단계에서 코드를 작성하도록 하겠다.

 

주변에서 가장 작은 원소는 0이기 때문에 해당 영역에서 만들 수 있는 가장 큰 사각형의 크기는 1이다.

 

그럼 그냥 넘어가도록 한다.

 

다음 영역에서 보았을 때다.

여기서 보았을 때 해당 2X2라는 가장 큰 정사각형을 만들 수 있다.

그러면 여기서 가장 큰 사각형을 2X2로 만들 수 있다고 해당 원소에 표시를 해주자.

가장 작은 원소의 수는 1이다.

그러면 여기서 가장작은 원소의 수 + 1을 해준다.

 

해당 부분을 검사하는 코드를 작성한다.

 

board[i][j] = min(board[i][j-1], board[i-1][j], board[i-1][j-1]) + 1
''' 해당 영역에서 가장 작은 수가 0을 원소로 가지는 칸이 있는 것이 min함수로 확인되면 
	board[i][j] = 0 + 1 '''

''' 해당 영역에서 가장 작은 수가 1을 원소로 가지는 칸이 있는 것이 min함수로 확인되면 
	board[i][j] = 1 + 1 '''

''' 해당 영역에서 가장 작은 수가 2을 원소로 가지는 칸이 있는 것이 min함수로 확인되면 
	board[i][j] = 2 + 1 '''

이렇게 해당 영역에서 보았을 때 만들 수 있는 가장 큰 정사각형은 2X2임을 알 수 있다.

여기서 만들 수 있는 가장 큰 정사각형이 2X2이므로 이를 메모해야한다.

메모 코드를 작성한다.

''' res 의 초기 값은 -inf로 한다.
res = float('-inf')
'''
board[i][j] = min(board[i][j-1], board[i-1][j], board[i-1][j-1]) + 1
res = max(res,board[i][j])

이렇게 메모를 하고 다음 인덱스로 넘어가자.

 

원소가 0인 인덱스는 그냥 넘어가는 조건문으로 바로 해당 원소로 가면 된다.

여기서 보았을 때, 딱히 만들 수 있는 정사각형이 없다.

2라고 메모를 해주었지만 신경쓸 필요 없다. 본질은 해당 칸이 정사각형을 만들 수 있는 지 없는지에 달려있기 때문이다.

해당 영역에서 가장 작은 원소의 크기가 0이므로 이 영역에서 만들 수 있는 정사각형의 크기는 1이다.

 

이러한 규칙을 적용하면 해당 전체 행렬의 크기가 더욱 커져도 똑같은 규칙을 이용해 메모이제이션을 하고 만들 수 있는 정사각형 크기들을 찾아내어 최종적으로 가장 큰 값을 출력하면 된다.

 

따라서 이에 해당하는 코드를 작성하면 다음과 같다.

 

def solution(board):
    res = float('-inf')
    # board[i][j] 로 보드를 나타낸다.
    for i in range(len(board)):
        for j in range(len(board[i])):
            if i == 0 or j == 0 or board[i][j] == 0:
                pass
            else:
                board[i][j] = min(board[i][j-1], board[i-1][j], board[i-1][j-1]) + 1
                res = max(res,board[i][j])
    return res * res

런타임 에러가 난다..

그러면 런타임 에러가 나는 이유를 분석해보자.

1. pass 때문인가?

=> pass 를 대신할 다른 문장을 찾아본다.

2. 행렬의 제한 크기 때문인가?

=> 문제에서 제한 크기로 제시하여서 괜찮다.

 

그렇다면 pass 문제만 해결하면 된다.

 

그냥 res값만 max함수를 이용해서 문제를 풀어보았다.

 

그러면 최종 답안은

 

모범답안

def solution(board):
    res = float('-inf')
    # board[i][j] 로 보드를 나타낸다.
    for i in range(len(board)):
        for j in range(len(board[i])):
            if i == 0 or j == 0 or board[i][j] == 0:
            	res = max(res,board[i][j])
                
            else:
                board[i][j] = min(board[i][j-1], board[i-1][j], board[i-1][j-1]) + 1
                res = max(res,board[i][j])
    return res * res

---