백준 14500문제 테트로미노

문제

N x M 크기의 값의 판에 입력값을 받았을때 아래 도형의 모양대로 집어넣어 가장 큰 수를 얻어내는것이 목표이다.

입력 예시
5 5

1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1

입력 예시와 같이 들어왔을때, 나올 수 있는 최대값은 19이다.

접근법

그러면 이제 이 문제를 접근하는 방식에 대해서 고려해보자.
나는 문제를 보자마자 떠오르는 방법이 명확했는데, 문제에서 제시한 모양의 개수가 그렇게 많지 않으므로, 나올 수 있는 경우의 수도 많지 않았다.
어느정도 계산해보면 결국 19개가 나왔는데, 해당 모양을 모든 장소에 대입해보면서 최대값을 찾아나가는 방법을 풀이로 풀었다.
그런데 다른 사람들이 푼 방법을 보니 DFS 해결법으로 풀었다는 이야기를 보고, 그 부분도 공부해봤다.

풀이법

그래서 내가 문제를 푼 방법은 간단했다. 다 대입해보는것이다.
입력 부분은 문제끼리 거의 비슷해서 통일되어있기도 하고, 궂이 설명이 필요가 없다.
그래서 나는 바로 문제 풀이의 핵심이 되는 코드만 적어보겠다.

for(int i=0;i<tetromino.length;i++){
            int tetris[][] = tetromino[i];
            for(int j=0; j<row; j++){
                continuePoint : for(int k=0; k<column; k++){
                    int sum = 0;
                    for(int l=0; l<4; l++){
                        if(j+tetris[l][0]>=row || k+tetris[l][1]>=column){
                            continue continuePoint;
                        }else{
                            sum += arr[j+tetris[l][0]][k+tetris[l][1]];
                        }
                    }
                    if(sum > max) max = sum;
                }
            }
        }

해당 코드를 한눈에 보면 이게 뭔가 싶을 수 있다.
그러면 코드에 붙은 덧살을 제거하고 처음부터 천천히 생각해보자.

for(int i=0;i<tetromino.length;i++){
            int tetris[][] = tetromino[i];
            for(int j=0; j<row; j++){
                continuePoint : for(int k=0; k<column; k++){
                    int sum = 0;
                    for(int l=0; l<4; l++){
                            sum += arr[j+tetris[l][0]][k+tetris[l][1]];
                    }
                    if(sum > max) max = sum;
                }
            }
        }

뭔가 줄어든 것 같은데 한눈에 들어오지 않는다. 일단 코드를 해석해보자.

for(int i=0;i<tetromino.length;i++){
            int tetris[][] = tetromino[i];
            for(int j=0; j<row; j++){

여기까지는 간단하다.
도형이 낼 수 있는 모든 경우가지수를 가지고 있는 3차원 배열의 변수를 모두 for문으로 돌려서, 하나하나 대조해보는것이다.
int tetris[][] 에 도형이 하나씩 들어가게 되는것이다.
이걸 맨 처음 입력받는 M, N으로 반복시켜 접근하면 된다.

for(int l=0; l<4; l++){
	sum += arr[j+tetris[l][0]][k+tetris[l][1]];
    }

자 그럼 아주 핵심적인 부분이다. continuePoint를 선언한 부분을 보기에 앞서, 내가 생각하기에 먼저 이해해야 하는 부분은 이부분이다. 보면 arr은 처음 입력받는 배열의 값을 가지고있고, 이것을 row,column에 접근하기만 하면 밸류값은 아주 쉽게 나온다. 거기에 tetris가 가지고있는 도형의 모양을 row, column형태로 가져와서 더하면 되기때문에 문제가 아주 쉬워진다.

그런데 문제가 있다. 이렇게 하면 분명히 잘 될 것 같다고 머리에서 생각하게 되는데, 이상하게 에러가 난다.

그렇다. Nullpointerexception이 뜬다.

아니 왜 그럴까?
간단하게 생각해보면 정말 쉬운게, 지금 우리가 만든 for문을 쉽게 보면 이런 느낌이다.

그림판으로 대충 만들었지만, 뭔 의미인지는 알 것이다.
그렇다면, 에러가 나는 경우는 어떤 경우일까?

바로 이 경우이다.
이것을 코드로 표현해보면 arr[0][5]가 되는데, arr은 0~4까지밖에 데이터가 없는데 5에 접근하려니 코드가 에러를 뱉는것이다. 그래서 우리는 이것을 걸러줘야하는데

                    if(j+tetris[l][0]>=row || k+tetris[l][1]>=column){

그렇다. 바로 이 코드가 그것을 걸러주는 역할을 하는것이다.
차근차근 보면 ,J(접근 데이터 Row값) 에 tetris[L(도형접근][0(Row)]를 더해 Row값이 Over했는지 검사하고
K(접근 데이터 Column값) 에 tetris[L(도형접근][1(Column)]를 더해 Column값이 Over했는지 검사한다.

이렇게 검사해서 만약 오버한 경우가 존재한다면, Continue를 해주는것이다.

그런데, Continue를 왜 하는지는 알았다. 어디에 해줘야 하지?

이 부분이 나에게는 상당히 고민거리였다.
왜냐면 continue를 내가 원하는곳에 하고싶은데, 만약 여기서 continue를 해버린다면 L값(도형에 접근하는값) 이 continue를 해버리기때문에 접근에서 그렇게 똑똑하다는 말은 할 수 없다.
물론 그냥 continue를 해줘도 작동은 한다.
왜? 이유도 간단하다. continue를 해줘서 더해야하는 값을 더하지 않으면 어차피 다른 모양이 1이라도 더 더하기때문에 다른 모양이 정답이 되므로, 최대값을 구하는 이 문제에서 그런 예외사항은 넘어만 가도 문제는 없다. 그러나, 이런 예외처리를 그렇게 단순하게 해버리면 그건 정답이라고 부르기 어렵다. 그래서 나는 for문을 원하는 장소에 시작시키기 위해

            continuePoint : for(int k=0; k<column; k++){
                int sum = 0;
                for(int l=0; l<4; l++){
                    if(j+tetris[l][0]>=row || k+tetris[l][1]>=column){
                        continue continuePoint;
                        

이런 코드를 짜게 된 것이다.

DFS 풀이법에 대해 설명을 고려하다 문득 나는 이 문제를 DFS로 풀지 않고 결국 답지를 봐버렸다.
이때까지 DFS가 뭔지 몰랐기 때문이다.
그러므로 다음 문제는 DFS로 푸는 문제를 가져와보도록 하겠다.