들어가는 말
2차원 벡터에서 1로 이루어진 정사각형의 크기를 찾는 문제다. 처음에는 아무리 생각해도 모르겠더라. 그래서 문제의 기본 아이디어를 찾아봤다.
현재 위치에서 대각선, 위쪽, 왼쪽이 0이 아니면 세 수 중 가장 작은 수에다가 1을 더해서 현재 위치에 저장하는 방식이었다.
어라? 어디서 많이 본 아이디어다 싶었더니 인공지능 공부할 때 배웠던 DP(동적 프로그래밍)이었다. DP란(저번에도 설명했지만) 처음부터 끝까지 계산을 해주는데 각 계산의 결과를 저장해놨다가 필요할 때 사용하는 방식이다.
여기서 조심해야 할 점은 DP의 첫 조건문은 대각선, 위쪽, 왼쪽이 0이 아니다가 아닌 현재 위치가 0이 아니다라는 것과 행과 열이 2보다 작은 경우에는 크기가 1이라는 점이다. 나는 저 두 개를 파악하지 못해서 한참 틀렸다. 나중에 통과했지만...
코드 설명
일단 최댓값을 비교해줘야 하니 answer에 board[0][0] 값을 넣어준다. 그리고 행과 열의 크기가 2보다 작을 경우는 answer이 1이라는(정사각형의 크기가 1) 조건을 넣어준다.
그 다음이 DP이다. for로 행과 열 이중반복문은 돌려준다. 이때 조심해야 할 것은 현재 위치가 0이 아니면 대각선, 위쪽, 왼쪽의 최솟값에다가 1을 더한 수를 현재값에 넣어줘야 한다는 거다. 대각선, 위쪽, 왼쪽이 0이면 안 된다가 아니다.
그렇게 현재 값을 구했다면 앞서 저장한 answer와 값을 비교한다. 만일 answer보다 값이 크다면 현재 값이 answer이 된다.
DP를 끝냈다면 answer에다가 answer을 곱해서 정사각형 크기를 반환하면 된다.
코드
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int solution(vector<vector<int>> board)
{
int answer = board[0][0];
int minn = 0;
if(board.size()<2 || board[0].size()<2){
answer = 1;
}
for(int i=1; i<board.size(); i++){
for(int j=1; j<board[0].size(); j++){
if(board[i][j]!=0){
minn = min(board[i-1][j-1], min(board[i-1][j], board[i][j-1]));
board[i][j] = minn + 1;
}
if(board[i][j] > answer){
answer = board[i][j];
}
}
}
answer = answer * answer;
return answer;
}참고
