[Baekjoon Online Judge] 1915 - 가장 큰 정사각형 / Java

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

1915번: 가장 큰 정사각형

풀이1

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int[][] map = new int[n][m];

		int answer = 0;
		for (int i = 0; i < n; i++) {
			String line = br.readLine();

			for (int j = 0; j < m; j++) {
				map[i][j] = line.charAt(j) - '0';
				if (map[i][j] == 1)
					answer = 1;
			}
		}

		for (int i = 1; i < n; i++) {
			for (int j = 1; j < m; j++) {
				if (map[i][j] == 1) {
					map[i][j] = Math.min(map[i - 1][j - 1], Math.min(map[i - 1][j], map[i][j - 1])) + 1;
					answer = Math.max(answer, map[i][j]);
				}
			}
		}

		System.out.println(answer * answer);
	}
}

풀이2

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int answer = 0;

		int[][] map = new int[n + 1][m + 1];

		for (int i = 1; i <= n; i++) {
			String str = br.readLine();
			for (int j = 1; j <= m; j++) {
				map[i][j] = str.charAt(j - 1) - '0';

				if (map[i][j] == 0) {
					continue;
				}

				int min = Integer.MIN_VALUE;

				map[i][j] = Math.min(map[i - 1][j - 1], Math.min(map[i - 1][j], map[i][j - 1])) + 1;

				answer = Math.max(answer, map[i][j]);
			}
		}

		System.out.println(answer * answer);
	}
}