백준 Q1051 - 숫자 정사각형

#Qustion : 코드에 질의가 있는 포스트

문제

N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

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

        for (int i = 0; i < row; i++) {
            String str = br.readLine();
            for (int j = 0; j < col; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }

        int len = Math.min(row, col);
        
        while (len > 1) {
            for (int i = 0; i <= row - len; i++) {
                for (int j = 0; j <= col - len; j++) { 
                    int a = map[i][j]; 
                    if (a == map[i][j + len - 1] && a == map[i + len - 1][j] && a == map[i + len - 1][j + len - 1]) {
                        System.out.println(len * len);
                        return;
                    }
                }
            }
            len--;
        }
        System.out.println(len * len);
    }

첫 번째 for문에서 입력을 받고
while 문에서 len 값을 감소시키며 정사각형의 넓이를 최대값에서 감소시키는 방식의 솔루션이다.

알고리즘에 있어서는 의문점이 없지만 테스트케이스를 복붙하지 않고 직접 입력해보는 과정에서 질문이 생겼다.

/**
* 3 5
* 4 2 1 0 1
* 2 3 1 1 0
* 2 2 1 1 0
*/

위 처럼 입력했을 경우 i=1, j=2에서 모든 모서리가 1로 같으므로
len = 2 => 2*2 = 4 가 출력되어야 한다.

즉 쉬운 예시를 들면

/** 
* 2 2           2 2
* 22            2 2
* 22            2 2
*/

왼쪽의 공백을 제거한 입력에서는 원하는 값인 4가 출력 되지만
오른쪽처럼 공백을 포함하면 4가 아닌 1이 출력된다.

StringTokenizer를 많이 사용해보지 않음에 따른 문제점인것 같은데,
정확한 이유는 잘 모르겠다

현재 시각 AM 04:52
5시에 첼시vs뉴캐슬 경기를 봐야해서 새벽에 일어나려 하긴 했지만
3시에 눈이 떠지는 바람에 뭘 할까 고민하다가 시험기간전에 풀지 못했던 백준 문제를 풀어봤는데
생각보다 킬링타임용으로 좋았던 것 같다

이후에 위에 의문점을 해결해보겠다.

아 그리고 새벽에 조금 적적해서 잔잔한 노래를 들으며 문제를 풀었는데 015B와 오웬의 노래인 "세월의 흔적 다 버리고" 라는 띵곡을 발견해서 기분이 좋다
새벽에 오웬의 노래가 딱 좋은거 같다