[백준] 가장 큰 정사각형

시험기간이라고 잠깐 쉬었는데, 보니까 엄청 오랜만이다. 다시 열심히 해보기.

문제

코드

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int main(){

	int n, m, max =0;
	string input;
	cin>>n>>m;
	int s[n][m];
	for(int i=0; i<n; i++){
		cin>>input;
		for(int j=0;j<m;j++){
			s[i][j] = input[j]-'0';
            if(s[i][j]==1){
                max =1;
            }
		}
	}
	
	for(int i=1; i<n; i++){
		for(int j=1;j<m;j++){
			if(s[i][j] != 0 ){
				int m = min(s[i-1][j], s[i][j-1]);
				s[i][j] = min(m, s[i-1][j-1])+1;
				
				if(s[i][j]>max){
					max = s[i][j];
				}
			}	
		}
	}
	

	if(n==1||m==1)
        cout<<1;
	else
		cout<<max*max;
}

이번 알고리즘 수업에서 dynamic programming 파트를 들으면서 나왔던 주제이다.
이 문제가 골드4 수준인 걸 보고, 알고리즘을 알고 있는 상태로 푸는 것과 백지 상태에서 스스로 생각해내는 것이 얼마나 큰 차이인지 느꼈다. 이 문제 풀이 방법을 이미 알고 있는 상태였기 때문에 코드만 작성하면 됐지만, 만약 아니었다면 내가 방법을 생각해낼 수 있었을지 의문이다.

idea

1. 탐색하고 있는 노드를 정사각형의 오른쪽 하단이라고 생각한다.
2. 해당 노드를 오른쪽 하단으로 하는 최대크기의 정사각형의 경우 d[i-1][j-1], d[i-1][j], d[i][j-1] 즉 노드 기준 상, 좌, 좌대각선에 있는 노드를 꼭지점으로 하는 최대 정사각형을 포함한다.
3. 즉 해당 칸에 들어갈 값은 min(d[i-1][j-1], d[i-1][j], d[i][j-1] )+1

이런 식으로 값을 업데이트 하면서 최종 결과를 구한다.

입력이 없는 경우나 매우 작은 경우를 생각 못해서 제출을 여러번 했는데, 이런 경우가 되게 사소하고 귀찮게 느껴져도 생각해보려고 노력해야겠다.