가장 큰 정사각형 (BJ_1915)

1. 문제 링크

https://www.acmicpc.net/problem/1915

---

 

2. 나의 코드

메모리: 102636	 kb
시간: 788 ms
코드 길이: 1229 B
시간 복잡도 : O(NM)
설명
- DP

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_1915 {

    static int[][] dp;
    static int N, M, result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        dp = new int[N][M];

        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split("");
            for (int j = 0; j < M; j++) {
                dp[i][j] = Integer.parseInt(input[j]);
            }
        }

        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {
                if (dp[i][j] == 1) {
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                result = Math.max(result, dp[i][j]);
            }
        }

        System.out.println((int)Math.pow(result, 2));
    }
}

 

 

---

 

3. 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[][] map = new int[N + 1][M + 1];
		for (int i = 1; i <= N; i++) {
			String[] input = br.readLine().split("");

			for (int j = 1; j <= M; j++) {
				map[i][j] = Integer.parseInt(input[j - 1]);
			}
		}

		// (0, 0)부터 (i, j)까지의 부분 합
		int[][] psum = new int[N + 1][M + 1];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				psum[i][j] = psum[i - 1][j] + psum[i][j - 1] - psum[i - 1][j - 1] + map[i][j];
			}
		}

		int ans = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				// 게임판의 숫자가 1이라면,
				if (map[i][j] == 1) {
					int res = 1;

					int idx = 1;

					// 2 x 2, 3 x 3, ... 사각형이 가능한지 탐색함.
					while (i + idx <= N && j + idx <= M) {
						// 특정 두 지점 사이의 부분 합
						int space = psum[i + idx][j + idx] - psum[i + idx][j - 1] - psum[i - 1][j + idx]
								+ psum[i - 1][j - 1];

						idx++;

						if (space != idx * idx) {
							break;
						}

						res = idx * idx;
					}

					ans = Math.max(ans, res);
				}
			}
		}

		bw.write(ans + "\n");
		bw.flush();
		bw.close();
		br.close();
	}

}

 

---

 

4. 배운 점

- 처음에는 DFS, 백트래킹을 생각했다. 문제 풀이 방법을 하나만 생각하면 시간낭비

- DP는 점화식이 너무 중요하다