[ 프로그래머스 ] LV.2 가장 큰 정사각형 찾기

 

 

 

 

// 문제 요약

 

0과 1이 채워진 2차원의 행렬이 주어지면

 

1로 만들 수 있는 정사각형중에 가장 큰 정사각형의 넓이를 구하여라

 

// 사고

 

기본적으로 생각할 수 있는 풀이는 DFS나 BFS다

 

그러나 효율성 문제를 보는 점이나 LV.2 인 것을 감안하면

 

DFS / BFS 가 아닐 가능성을 생각해야한다.

 

이 문제의 풀이는 greedy로 푸는 것이다.

 

정사각형을 구성하는 가장 작은 단위는 2x2 정사각형이다.

 

이 단위정사각형을 필터로 하여 훑으면서 지나가는데

 

모든 값은 0과 1로 주어지므로 단위 정사각형이 구성될 경우

 

정사각형 내의 값을 아무리 크게 업데이트 해줘도

 

움직인 필터에서 구성되지 않을 경우의 minimum값은 여전히 0이다.

 

이 성질을 이용해서 누적해가면서 정사각형이 구성되는 경우를 구하면 된다.

 

코드를 보자.

 

 

 

 

// 풀이

 

https://github.com/hyun06000/coding_test_study_with_python/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/level_check/LV2/%EA%B0%80%EC%9E%A5%20%ED%81%B0%20%EC%A0%95%EC%82%AC%EA%B0%81%ED%98%95%20%EC%B0%BE%EA%B8%B0.py

hyun06000/coding_test_study_with_python

 

def solution(board):
    I = len(board)
    J = len(board[0])

    for i in range(I - 1):
        for j in range(J - 1):
            if board[i + 1][j + 1]:
                board[i + 1][j + 1] += min(board[i][j], board[i + 1][j], board[i][j + 1])

    k = 0
    for b in board:
        k = max(max(b), k)

    return k ** 2

 

 

주의할 점은 업데이트할 위치의 값을 포함하여 min을 구하는 경우인데

 

이때는 다른 값이 2나 3이더라도 자기 자신이 1이기 때문에 min 값은 1이된다. 

 

따라서 이 부분을 빼고 min을 구해준다.

 

이것만 조심하면 효율성 테스트까지 모두 맞출 수 있는 문제다.