[알고리즘][파이썬] 백준 1915번 - 가장 큰 정사각형

---

처음 떠올렸던 접근 방법

1. dp를 활용해서 해당 인덱스에서 구성될 수 있는 최대 정사각형 크기(가로 혹은 세로 길이)를 저장한다.
2. [0][0] 부터 [n][m]까지 모든 경우의 수를 확인한다.

개선된 접근 방법

1. 정사각형의 맨 오른쪽 맨 아래의 사각형을 기준으로 [0][0]에서 대각선으로 [n][m]까지 뻗어나가며 최대가 될 수 있는 정사각형의 크기를 저장한다.
2. [0][0] 부터 [n][m]까지 모든 경우의 수를 확인한다.

2x2의 경우 가로세로가 2가 되므로 오른쪽 아래 사각형에 2를 저장한다.

3x3의 경우 최대는 3이며 3x3 내부에서 2x2크기의 사각형들이 존재하므로 각각의 정사각형에서 오른쪽 아래의 사각형에 크기(이 경우 2)를 저장한다.

4x4의 경우 최대는 4이며 4x4 내부에서 2x2크기의 정사각형들과 3x3 정사각형들이 존재하므로 이전과 마찬가지로 크기를 저장해둔다.

---

최종 입력 코드

Y, X = map(int, input().split())
graph = []
for _ in range(Y):
    graph.append(list(map(int, list(input()))))
result = 0

for i in range(Y):
    for j in range(X):
        if i > 0 and j > 0 and graph[i][j] == 1:
            graph[i][j] += min(graph[i][j-1], graph[i-1][j], graph[i-1][j-1])
        result = max(result, graph[i][j])
print(result*result)

---

사실 문제를 풀기 전에 입력을 받는 부분에서부터 어려움이 있었다..
이 문제의 경우 0100, 0111 ... 이렇게 이진수처럼 문자형 숫자들이 입력이 되는데, 이를 리스트에 추가할 때 어떻게 해야할지 난감했다.

list(map(int, list(input())))

이렇게 하면 입력이 문자형이므로 ['0', '1', '0', '0'] 이런식으로 분할이 되어 리스트에 담기게 되고, map함수로 인해 각각의 숫자들이 int 형으로 변환이 된다.

잘 알아두어야겠다.