[프로그래머스, JAVA, 다시풀어보기] 가장 큰 정사각형 찾기

 

저의 DFS로 풀려는 아이디어로는 시간 초과와 1000 이상의 값에서는 절대 돌아가지 않을 것 같다는 판단에 다른 분들의 아이디어를
보고 이해한 후에 배껴서 풀었습니다. 아이디어 잘 생각 하시는 분들 보면 정말 부럽... 하지만 재능이 나무에서 뚝 떨어지신 분들도 
많겠지만 저에게는 그러한 재능이 없기에.. 꾸준히 높이 뛰기해서 쟁취해야겠죠 잡설이 길었습니다.

조건 두 개를 주었습니다.

1. 표의 가로나 세로 크기가 1일 경우 => 이 경우, 정사각형의 원리에 의해 1인 값이 하나라도 있으면 넓이는 1일 수 밖에 없습니다.
   모두 0 이면 당연히 0을 출력하겠죠
2. 가로 세로 모두 2 이상일 경우, 1,1에서 부터 시작한다. => 정사각형의 한변의 크기를 구하는 원리에 의해 
   
   출처: https://blog.sonim1.com/212 [Kendrick's Blog]

배열에서 가장 큰 정사각형 찾기

 

• 배열의 [1][1]부터 반복문을 돌린다. (첫 번째 행, 첫 번째 열 무시, 이유는 2번 참고)
• 현재 값이 1일 경우, 좌측값, 상단값, 좌측상단값 중 가장 작은 값의 +1 한 값을 현재 값으로 할당.
• 배열이 끝날 때 까지 반복.
• 배열의 가장 큰 값이 현재 배열의 가장 큰 정사각형의 값이 된다.

 

아래는 제가 푼 코드입니다.

class Solution {
	static boolean[][] visited;
	static boolean[] widthVisited;
	static boolean[] heightVisited;

	static int[][] map;
	static int max = Integer.MIN_VALUE;
	static int height;
	static int width;

	public int solution(int[][] board) {
		int answer = 1234;

		height = board.length;
		width = board[0].length;
		map = board;

		heightVisited = new boolean[height];
		widthVisited = new boolean[width];
		visited = new boolean[height][width];
		
		if(height == 1) {
			for(int i=0;i<width;i++) {
				if(map[0][i] == 1)
					return 1;
			}
			
			return 0;
		}
		
		if(width == 1) {
			for(int i=0;i<height;i++) {
				if(map[i][0] == 1) 
					return 1;
			}
			
			return 0;
		}

		for (int i = 1; i < height; i++) {
			for (int j = 1; j < width; j++) {
				if (map[i][j] == 1) {
					int min = Math.min(Math.min(map[i][j - 1], map[i - 1][j]), map[i - 1][j - 1]);
					min++;
					map[i][j] = min;

					if (max < min * min) {
						max = min * min;
					}
				}
			}
		}

		answer = max;

		return answer;
	}
}

지저분하고 한눈에 들어오지 않는 코드이며, 저만의 아이디어가 아닌 다른 분의 아이디어에 힌트를 얻어 푼 문제입니다. 나중에 이 문제를 
다시한번 도전해야겠습니다. DP.. 이 초보자에겐 너무 어렵습니다..