테트로미노(백준_14500)

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

14500번: 테트로미노

문제 설명

입력

• 첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)
• 둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

시간제한은 2초이므로 2억 번 연산이 가능하다고 생각하자. 전체 최대 수가 500 * 500 = 250000개이다. 2억 번을 250000으로 나누면 800이므로 하나의 수당 800번 연산도 가능하다는 것이므로 완전 탐색을 해도 되겠다는 힌트를 얻었다.

 

문제에 대한 아이디어

이 문제는 2차원 배열이 주어지면 테트로미노를 2차원 배열에 올려놀 때 테트로미노 안에 있는 수들의 합 중 최대 수를 구하는 것이다. 아이디어는 굉장히 쉽다. 테트로미노 모양처럼 완전탐색을 하면 된다.

• 처음 4가지 모양

이 4가지 모양은 한 지점에서 시작하여 상하좌우 탐색으로 돌아다니면서 모양을 만들 수 있다. 한 지점에서 시작하여 카운트가 4가 될 때까지 상하좌우 탐색을 해보면 무조건 이 4가지 모양중 하나가 만들어진다. 

• 마지막 모양

마지막 모양은 왼쪽 그림처럼 한번에 상하좌우 탐색으로 만들어질 수 없는 모양이다. 그래서 마지막 모양만 다르게 구하기로 했다. 오른쪽 그림처럼 1번에서 시작하여 2,3,4,5 중에 3개만 고르는 것이다. 그러면 마지막 모양이 되므로 문제에 조건을 만족한다.

 

구현

• static 변수들

static int result=0; //결과값
static int n,m; 
static boolean visited[][]; //방문했는지 검사
static int arr[][]; //주어지는 2차원 배열
static int dx[] = {-1,1,0,0}; //x 축 상하좌우
static int dy[] = {0,0,-1,1}; //y 축 상하좌우

• solve : 처음 4가지 모양에 대한 탐색

public static void solve(int y, int x, int count, int sum){
        //4개 다 조사했으면 결과 값 검사하기
        if(count == 4){
            result = Math.max(result, sum);
            return;
        }
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            //경계 지나가면 다음꺼로 넘어가기
            if(ny < 0 || ny >= n || nx < 0 || nx >= m){
                continue;
            }
            //방문 안했으면 상하좌우 탐색
            if(!visited[ny][nx]){
                visited[ny][nx] = true;
                solve(ny, nx,count+1, sum +arr[ny][nx]);
                visited[ny][nx] = false;
            }
        }
    }

매개변수는 y(행), x(열), count(몇개), sum(지금 까지 합)이다.

• solve2 : 마지막 모양 탐색

public static void solve2(int y, int x, int sum, int count, int start){
    //3개를 골랐으면 마무리
    if(count == 3){
        result = Math.max(result, sum);
        return;
    }
    for (int i = start; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || ny >= n || nx < 0 || nx >= m){
            continue;
        }
        solve2(y, x, sum+arr[ny][nx], count+1, i+1);
    }
}

solve와 다른점은 매개변수가 다르다. 4개중에 3개를 선택하면 되므로 for문의 시작부분을 변경해주었다. 쉽게 생각해보면 시작점에서 조사해봐야 할 곳은 (좌, 상, 우) (상, 우, 하), (우, 하, 좌), (하, 좌, 상) 이렇게 4개만 존재한다. 그러므로 for문 시작 값을 전에 조사했던 for문 보다 하나씩 올려서 조사해 겹치치 않게 하면 아래 그림처럼 4개를 조사하게 된다.

 

전체 코드

https://github.com/Heron-Woong/CodingTest_Practice/commit/20bdd2edfa387a1e150f4251d25625afa4191818

백준_14500, 테트로미노 · Heron-Woong/CodingTest_Practice@20bdd2e