728x90
반응형
문제:
1과 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요.( 단, 정사각형이란 축에 평행한 정사각형을 말합니다.)
풀이 방법:
이 문제는 DP(dynamic programming), 동적계획법을 사용해서 풀어야 하는 문제이다. 왼쪽 위(1,1)부터 시작해서 오른쪽 아래로 진행을 하면서 정사각형을 나간다.
정사각형으로 취급되는 경우는 다음과 같다.
1(1번) |
1(2번) |
1(3번) |
1(4번) |
4번의 값이 0이 아니라면 1,2,3번의 값을 비교해 최소값을 찾은 뒤에 4번 자리에 그 최솟값에 1을 더한 값을 넣어 준다. 즉 다음과 같이 된다.
1(1번) | 1(2번) |
1(3번) | 2(4번) |
최솟값을 찾는 이유는 하나의 0이 있다면 정사각형의 형태가 아니므로 1 이상의 값들만 이어나가기 위함이다. 또한 1을 더해주는 이유는 정사각형이라면 길이의 값을 누적하기 위해서이고 아니라면 남은 1의 값들이 다른 곳에서 정사각형을 이룰 수 있기 때문에 이어나가주는 것이다.
이 문제의 예시를 통해서 구하는 방법을 알아보자. 다음과 같이 처음 상태가 있다.
0 |
1 |
1 | 1 |
1 |
1 |
1 | 1 |
1 |
1 |
1 | 1 |
0 | 0 | 1 | 0 |
처음 왼쪽 위 (1,1)을 비교해 보았을 때 (0,0)이 0이기에 (1,1)의 값을 1로 바꾼다.
0 | 1 | 1 | 1 |
1 | 1 | 1 | 1 |
1 | 1 | 1 | 1 |
0 | 0 | 1 | 0 |
(1,2)의 값을 비교해 보았을 때 주위 최솟값이 1이므로 (1,2)의 값을 2로 바꾼다. 이 경우가 길이가 2인 정사각형을 찾은 경우이다. 하지만 가장 큰 정사각형을 찾는 것이 문제이므로 계속 탐색해보도록 한다.
0 | 1 | 1 | 1 |
1 | 1 | 2 | 1 |
1 | 1 | 1 | 1 |
0 | 0 | 1 | 0 |
(1,3)의 값을 비교해보았을 때, 주위 최솟값이 1이므로 (1,3)의 값을 2로 바꾼다. 이 경우도 역시 길이가 2인 정사각형을 찾은 경우다. 이전 (1,2)에서도 정사각형을 찾았지만 이 둘로는 정사각형이 아닌 직사각형이 만들어지므로 서로 영향을 주진 못한다.
0 | 1 | 1 | 1 |
1 | 1 | 2 | 2 |
1 | 1 | 1 | 1 |
0 | 0 | 1 | 0 |
계속해서 이 방법대로 진행을 하면 (2,2)까지 다음과 같이 표를 바꿀 수 있다.
0 | 1 | 1 | 1 |
1 | 1 | 2 | 2 |
1 | 2 | 2 | 1 |
0 | 0 | 1 | 0 |
(2,3)에서는 주위의 최솟값이 2이므로 (2,3)의 값을 3으로 바꾼다 즉 길이가 3인 정사각형을 찾은 경우다. 이 처럼 주위의 값들이 모두 2,2,2 혹은 3,3,3 과 같이 이루어져 있을 경우에 가장 큰 정사각형의 길이가 바뀌게 되는 것이다.
0 | 1 | 1 | 1 |
1 | 1 | 2 | 2 |
1 | 2 | 2 | 3 |
0 | 0 | 1 | 0 |
마지막 줄은 계속 진행해보아도 변경되는 점이 없으므로 이 예시의 가장 큰 정사각형은 길이가 3인 정사각형이다.
다른 채점케이스에서 전부다 0인 경우에는 위와 같은 방법으로 길이가 1인 정사각형이 있다고 나오므로 따로 구분해서 구하도록 하였다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | def solution(board): max_point=0 for i in range(len(board)): max_point+=sum(board[i][:]) if max_point==0: return 0 max_point=0 for i in range(1,len(board)): for j in range(1,len(board[0])): if board[i][j]==0: continue else: min_point=min(board[i][j-1],board[i-1][j],board[i-1][j-1]) min_point+=1 board[i][j]=min_point if max_point < board[i][j]: max_point=board[i][j] if max_point==0: return 1 else: return max_point**2 | cs |
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [Programmers]Lv 1. 체육복(테스트케이스 수정) (0) | 2019.03.03 |
|---|---|
| [Programmers]Lv 3. 이중우선순위큐 (1) | 2019.03.03 |
| [Programmers]Lv 3. 입국 심사 (2) | 2019.03.01 |
| [Programmers]Lv 2. 타겟 넘버 (0) | 2019.02.28 |
| [Programmers]Lv 3. 정수 삼각형 (0) | 2019.02.27 |