티스토리 뷰
728x90


문제 풀이 과정
이 문제는 탐색을 통해서 해결해한다. 다이나믹 프로그래밍으로 해결 하기위해서는 우선 dp 용 배열을 하나 만들어 둔다.
탐색 할때 첫번째 행과 열일 때는 별도의 탐색을 하지 않는다
첫번째 열과 행이 아니면서 1일때는 현재 기준으로 위, 왼쪽, 왼쪽 대각선의 값을 확인 해봐야한다.
그 중에서 최소값에다가 + 1을 한 값이 사각형의 크기가 된다.

(1, 1) 인 경우에는 현재값이 1이라 위, 왼쪽, 왼쪽 대각선의 값을 비교해야한다.
이 세개의 최소 값은 0 이고 이 값에 + 1한 값은 1이 된다.

(2, 2) 일때는 위, 왼쪽, 왼쪽 대각선의 값의 최솟값이 1이며, 이 값에 + 1 하면 2가 된다. 여기서 나온 2는 이 사각형의 크기가 된다.
전체 코드
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.io.BufferedReader; | |
import java.io.IOException; | |
import java.io.InputStreamReader; | |
import java.util.StringTokenizer; | |
public class Main { | |
public static int solution(int[][] matrix) { | |
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { | |
return -1; | |
} | |
int maxVal = 0; | |
int[][] dp = new int[matrix.length][matrix[0].length]; | |
for (int i = 0; i < matrix.length; i++) { | |
for (int j = 0; j < matrix[i].length; j++) { | |
dp[i][j] = matrix[i][j]; | |
if(i != 0 && j != 0 && dp[i][j] != 0){ | |
int up = dp[i][j - 1]; | |
int left = dp[(i - 1)][j]; | |
int ul = dp[(i - 1)][j - 1]; | |
int minVal = Math.min(Math.min(up, left), ul); | |
dp[i][j] = minVal + 1; | |
} | |
maxVal = Math.max(maxVal, dp[i][j]); | |
} | |
} | |
return maxVal * maxVal; | |
} | |
public static void main(String[] args) throws IOException { | |
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[][] data = new int[n][m]; | |
for (int i = 0; i < n; i++) { | |
String temp = br.readLine(); | |
for (int j = 0; j < m; j++) { | |
data[i][j] = Integer.parseInt(temp.substring(j, j + 1)); | |
} | |
} | |
System.out.println(solution(data)); | |
} | |
} |

728x90
'Algorithm > Baekjoon' 카테고리의 다른 글
백준 11404번 - 플로이드 (JAVA) (0) | 2023.01.19 |
---|---|
백준 16120번 - PPAP (JAVA) (0) | 2023.01.18 |
백준 1484번 - 다이어트 (JAVA) (0) | 2023.01.17 |
백준 2437번 - 저울 (JAVA) (0) | 2023.01.17 |
백준 4386번 - 별자리 만들기 (JAVA) (1) | 2023.01.11 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 프로그래머스 자바
- 백준
- 코딩테스트 공부
- 프로그래머스
- 개발자 취업 준비
- 프로그래머스 카카오
- 코딩테스트
- 알고리즘 공부
- 코테준비
- 알고리즘
- 백엔드 개발자
- 주니어 개발자 취업 준비
- java
- 알고리즘공부
- 백엔드 개발자 기술 면접 준비
- 기술 면접 준비
- 코테공부
- 개발자 면접 준비
- 자바
- 취준
- 취업 준비
- 코딩테스트공부
- 개발자 취준
- 제로베이스 백엔드 스쿨
- 코딩테스트 준비
- 코테 준비
- 취업준비
- 제로베이스 백준 장학금
- 백엔드 개발자 취업 준비
- 자바공부
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
글 보관함