ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 4095
    알고리즘/acmicpc 2016. 8. 15. 21:54

    행렬안에서 1로 이루어진 최대 정사각형을 찾는문제.


    가장 쉽게 생각한다면 모든 점에서 만들 수 있는 최대 정사각형을 탐색해보는 방법이 있지만 이럴경우 O(N^4)로 시간초과가 날 수 밖에 없다. 하지만 구하고자하는 사각형의 형태가 정사각형인점을 잘 이용하면 다이나믹 프로그래밍을 이용해 O(N^2)안에 해결 할 수 있다.


    어떠한 위치에서 정사각형을 만들 때, 이전에 만들어진 정사각형의 정보를 활용할 수 있는 방법을 생각해보자.


    4번(X, Y) 위치를 꼭지점으로 하는 정사각형을 만들려고하자. 그러면 4번위치 주위에 1, 2, 3번의 사각형들을 생각해볼 수 있다.


    - 1번은 (X-1, Y-1)을 오른쪽 아래 꼭지점으로 할 때 가장 큰 정사각형이다.

    - 2번은 4번에서 위로 그을 수 있는 최대 선분의 길이다.

    - 3번은 4번에서 왼쪽으로 그을 수 있는 최대 선분의 길이다.


    4번 위치를 꼭지점으로 하는 정사각형은 1, 2, 3번 사각형의 조합으로 만들어진다. 여기서 1, 2, 3번의 각각의 선분의 크기를 비교해가면서 다음과 같이 점화식을 정해줄 수 있다.


    dp[x][y] = min(row[x][y], col[x][y], dp[x-1][y-1]+1)  



     
    #include<stdio.h>
    #define MAX 1001
    
    #define MIN(a, b) ((a) < (b) ? (a) : (b))
    
    int dp[MAX][MAX];
    int conti[MAX][MAX][2];	// row : 0, col : 1
    
    int map[MAX][MAX];
    
    int main() {
    	int R, C;
    	int i, j, ans;
    
    	while (1) {
    		scanf("%d %d", &R, &C);
    
    		ans = 0;
    
    		if (R == 0 && C == 0)
    			break;
    
    		for (i = 1; i <= R; i++)
    			for (j = 1; j <= C; j++) {
    				scanf("%d", &map[i][j]);
    				dp[i][j] = conti[i][j][0] = conti[i][j][1] = 0;
    			}
    
    
    		for (i = 1; i <= R; i++)
    			for (j = 1; j <= C; j++) {
    				if (!map[i][j])
    					continue;
    				conti[i][j][0] = conti[i - 1][j][0] + 1;
    				conti[i][j][1] = conti[i][j - 1][1] + 1;
    
    				dp[i][j] = MIN(dp[i - 1][j - 1] + 1, MIN(conti[i][j][0], conti[i][j][1]));
    
    				if (dp[i][j] > ans)
    					ans = dp[i][j];
    			}
    
    		printf("%d\n", ans);
    	}
    
    	return 0;
    }
    

    '알고리즘 > acmicpc' 카테고리의 다른 글

    10422  (0) 2017.04.05
    1937  (0) 2016.09.06
    4095  (0) 2016.08.15
    11437  (0) 2016.07.30
    2253  (0) 2016.07.24
    11049  (0) 2016.07.24

    댓글 0

Designed by Tistory.