[Baekjoon Online Judge] 백준 1915번 가장 큰 정사각형(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1915번 가장 큰 정사각형

(C++, Python)

(글쓴날 : 2020.04.24)

 

---

* Baekjoon Online Judge, 백준 1915번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1915번 가장 큰 정사각형

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

---

2) 풀이 과정

* 시간 복잡도 : O(nm)

 

0과 1이 들어있는 n X m 크기의 배열이 주어질 때, 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 문제입니다.

 

저의 경우, 동적 계획법을 적용하였으며, C++과 Python을 사용했습니다.

특별히 memoization을 위한 테이블을 따로 만들지는 않았고, 주어진 배열을 완전 탐색하여 현재 인덱스가 1일 시, 해당 인덱스 기준 왼쪽, 왼쪽 상단 대각선, 위쪽 값을 조사해 만약, 0이 아니면 변이 이어진 경우이므로 미리 만들어 놓은 임시 리스트에 저장하였습니다.

그 후, 리스트의 길이가 3이면 정사각형의 모든 변이 이어져있으므로 리스트에 담긴 최솟값 + 1을 다시 현재 위치의 인덱스에 기록해가는 방법으로 최대 길이를 구해 문제를 해결했습니다.

단, 문제에서 주어지는 입력값이 string이므로, 문자열 그대로 입력받아 저장한 Python은 리스트의 길이가 3이 아닐 시 현재 값을 int 타입으로 형변환 하는 작업을 추가로 해주었고, C++의 경우, 애초에 입력받을 당시 미리 int 타입으로 변환해 저장하였으므로 생략했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
int arr[1001][1001];
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0, m = 0;
    cin >> n >> m;
 
    string temp = "";
    for (int i = 0; i < n; i++)
    {
        temp = "";
        cin >> temp;
        for (int j = 0; j < m; j++)
            arr[i][j] = temp[j] - '0';
    }
 
    int dx[4] = {-1, 0, -1}, dy[4] = {0, -1, -1};
    int maxLength = 0;
 
    vector<int> length;
    int countLength = 0;
    int minLength = 0;
    int ii = 0;
    int jj = 0;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (arr[i][j] == 1)
            {
                length.clear();
 
                for (int way = 0; way < 3; way++)
                {
                    ii = i + dx[way];
                    jj = j + dy[way];
 
                    if (ii < 0 || ii > n - 1 || jj < 0 || jj > m - 1)
                        continue;
                    if (arr[ii][jj] && arr[ii][jj] != 0)
                        length.push_back(arr[ii][jj]);
 
                    countLength = length.size();
                }
 
                if (countLength)
                    minLength = *min_element(length.begin(), length.end());
                else
                    minLength = 0;
 
                if (countLength == 3)
                    arr[i][j] = minLength + 1;
 
                if (maxLength < arr[i][j])
                    maxLength = arr[i][j];
            }
        }
    }
 
    cout << pow(maxLength, 2);
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
n, m = map(int, input().split())
arr = [list(input().rstrip()) for _ in range(n)]
dx, dy = [-1, 0, -1], [0, -1, -1]
maxLength = 0
 
for i in range(n):
    for j in range(m):
        if arr[i][j] == '1':
            length = []
 
            for way in range(3):
                ii = i + dx[way]
                jj = j + dy[way]
 
                if ii < 0 or ii > n - 1 or jj < 0 or jj > m - 1:
                    continue
 
                if arr[ii][jj] and arr[ii][jj] != '0':
                    length.append(int(arr[ii][jj]))
            
            countLength = len(length)
            if countLength:
                minLength = min(length)
            else:
                minLength = 0
 
            if countLength == 3:
                arr[i][j] = minLength + 1
            else:
                arr[i][j] = int(arr[i][j])
 
            if maxLength < arr[i][j]:
                maxLength = arr[i][j]
 
print(maxLength ** 2)

---