[백준/구현/C++] 14500번 테트로미노

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

14500번: 테트로미노

문제 해결 방법

이 문제는 T모양과 나머지 모양을 따로 구현했다. 각 모양마다 구한 코드도 있었는데 나는 두가지 방법으로만 구현했다.

 

1. T제외 4가지 모양 구하기 (make() 함수)

이건 백트래킹을 사용해서 구현했다. 

상하좌우를 탐색하며 범위가 넘어갔을때는 제외하고 4칸째일때 4수의 합과 최대값을 비교한다

// x좌표, y좌표, 칸들의 합, 몇번째 방문한 칸인지
void make(int x, int y, long long int tot, int count){
    if(count==4){ // 4칸째일 때 리턴
        result = max(result, tot); // 더한 값과 최대값 비교
        return;
    }

    for(int i=0; i<4; i++){
        int nx = x + dx[i]; // 상하좌우 탐색
        int ny = y + dy[i];

        // 범위를 벗어나면 무시
        if(nx>n || nx<0 || ny>m || ny<0) continue;

        if(!isvisited[nx][ny]){
            isvisited[nx][ny] = true;
            make(nx, ny, tot+mapp[nx][ny], count+1);
            isvisited[nx][ny] = false;
        }
    }
}

 

2. T모양 구현 (makeT() 함수)

일단 위 그림처럼 좌표를 만들어 준다

int t1[4][2] = {{0,0},{0,1},{0,2},{1,1}};
int t2[4][2] = {{0,0},{1,0},{2,0},{1,1}};
int t3[4][2] = {{0,1},{1,0},{1,1},{1,2}};
int t4[4][2] = {{0,1},{1,0},{1,1},{2,1}};

 x, y 좌표가 범위 밖으로 벗어나지 않게 for문을 돌려 최대값의 합과 비교해준다

void makeT(){
    // t1
    for(int i=0; i<n-1; i++){
        for(int j=0; j<m-2; j++){
            result = max(result, mapp[t1[0][0]+i][t1[0][1]+j] + mapp[t1[1][0]+i][t1[1][1]+j] + mapp[t1[2][0]+i][t1[2][1]+j] + mapp[t1[3][0]+i][t1[3][1]+j]);
        }
    }
    // t2
    for(int i=0; i<n-2; i++){
        for(int j=0; j<m-1; j++){
            result = max(result, mapp[t2[0][0]+i][t2[0][1]+j] + mapp[t2[1][0]+i][t2[1][1]+j] + mapp[t2[2][0]+i][t2[2][1]+j] + mapp[t2[3][0]+i][t2[3][1]+j]);
        }
    }
    // t3
    for(int i=0; i<n-1; i++){
        for(int j=0; j<m-2; j++){
            result = max(result, mapp[t3[0][0]+i][t3[0][1]+j] + mapp[t3[1][0]+i][t3[1][1]+j] + mapp[t3[2][0]+i][t3[2][1]+j] + mapp[t3[3][0]+i][t3[3][1]+j]);
        }
    }
    // t4
    for(int i=0; i<n-2; i++){
        for(int j=0; j<m-1; j++){
            result = max(result, mapp[t4[0][0]+i][t4[0][1]+j] + mapp[t4[1][0]+i][t4[1][1]+j] + mapp[t4[2][0]+i][t4[2][1]+j] + mapp[t4[3][0]+i][t4[3][1]+j]);
        }
    }
}

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int n, m;
long long int mapp[501][501];
long long int result = 0;
int dx[] = {-1, 1, 0, 0}; // 왼쪽, 오른쪽, 위, 아래
int dy[] = {0, 0, 1, -1};
bool isvisited[501][501];
int t1[4][2] = {{0,0},{0,1},{0,2},{1,1}};
int t2[4][2] = {{0,0},{1,0},{2,0},{1,1}};
int t3[4][2] = {{0,1},{1,0},{1,1},{1,2}};
int t4[4][2] = {{0,1},{1,0},{1,1},{2,1}};

// x좌표, y좌표, 칸들의 합, 몇번째 방문한 칸인지
void make(int x, int y, long long int tot, int count){
    if(count==4){ // 4칸째일 때 리턴
        result = max(result, tot); // 더한 값과 최대값 비교
        return;
    }

    for(int i=0; i<4; i++){
        int nx = x + dx[i]; // 상하좌우 탐색
        int ny = y + dy[i];

        // 범위를 벗어나면 무시
        if(nx>n || nx<0 || ny>m || ny<0) continue;

        if(!isvisited[nx][ny]){
            isvisited[nx][ny] = true;
            make(nx, ny, tot+mapp[nx][ny], count+1);
            isvisited[nx][ny] = false;
        }
    }
}

void makeT(){
    // t1
    for(int i=0; i<n-1; i++){
        for(int j=0; j<m-2; j++){
            result = max(result, mapp[t1[0][0]+i][t1[0][1]+j] + mapp[t1[1][0]+i][t1[1][1]+j] + mapp[t1[2][0]+i][t1[2][1]+j] + mapp[t1[3][0]+i][t1[3][1]+j]);
        }
    }
    // t2
    for(int i=0; i<n-2; i++){
        for(int j=0; j<m-1; j++){
            result = max(result, mapp[t2[0][0]+i][t2[0][1]+j] + mapp[t2[1][0]+i][t2[1][1]+j] + mapp[t2[2][0]+i][t2[2][1]+j] + mapp[t2[3][0]+i][t2[3][1]+j]);
        }
    }
    // t3
    for(int i=0; i<n-1; i++){
        for(int j=0; j<m-2; j++){
            result = max(result, mapp[t3[0][0]+i][t3[0][1]+j] + mapp[t3[1][0]+i][t3[1][1]+j] + mapp[t3[2][0]+i][t3[2][1]+j] + mapp[t3[3][0]+i][t3[3][1]+j]);
        }
    }
    // t4
    for(int i=0; i<n-2; i++){
        for(int j=0; j<m-1; j++){
            result = max(result, mapp[t4[0][0]+i][t4[0][1]+j] + mapp[t4[1][0]+i][t4[1][1]+j] + mapp[t4[2][0]+i][t4[2][1]+j] + mapp[t4[3][0]+i][t4[3][1]+j]);
        }
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> mapp[i][j];
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            isvisited[i][j] = true;
            make(i, j, mapp[i][j], 1);
            isvisited[i][j] = false;
        }
    }
    makeT();

    cout << result;

    return 0;
}