14500번 테트로미노

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

테트로미노 삼성 기출 문제.

첫번쨰 생각.

ㅗ 모양 블럭을 제외하면 나머지는 dfs를 돌릴 수 있을 것 같다.

그런데 문제는, ㅗ 모양이다. ㅗ 모양을 4방향으로 회전한 모양 ㅓ ㅏ ㅜ ㅗ 이것들은 따로 처리를 해줘야 할 것 같다. 모든 점에 대해서 dfs를 돌린다. 이 dfs는 깊이 4에 도달하면 그때 dfs에서 여태 지나온 점들의 합을 계산해서 최대값을 갱신한다. 이런 방식을 쓰면 해당 점에서 얻을 수 있는 최대 점수가 나온다. 이런 방식으로 모든 점에 대해서 dfs를 반복하면 값을 구할 수 있을 것 같다.

위 생각대로 구현 해봤다. 맞았다. 전체 모든 점에서 모든 가능한 블록의 경우의 수를 다 해본다음. 최대값을 마지막에 출력하면 된다.

주의할점은. dfs를 돌리는거기 때문에 방문을 체크해줘야 무한루프가 돌지 않는다는 것이고, dfs에서 빠져 나올때 방문 체크를 해제 해주어야 다음 점에서 모든 경우의 수를 돌릴때 방해가 되지 않는다는 점이다.

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <vector>
#include <utility>
using namespace std;
int map[501][501];
bool visit[501][501];
int n,m;
#define FOR(i,a,b) for(int i=a; i<b; i++)
inline bool is_in(int x,int y){ return x>=0 && x<n && y>=0 && y<m;}
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int answer = -1;

void dfs(int x,int y,int sum,int depth){
    visit[x][y] = true;
    if(depth == 4){
        answer = max(sum,answer);
        visit[x][y] = false;
        return;
    }
    FOR(i,0,4){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(is_in(nx,ny)){
            if(!visit[nx][ny]){
                dfs(nx,ny,sum+map[nx][ny],depth+1);
            }
        }
    }
    visit[x][y] = false;
}

vector<vector<pair<int,int>>> v
        { { {0,-1}, {0,1}, {-1,0}}, //ㅗ모양
          {{-1,0}, {1,0}, {0,1}}, //ㅏ모양
          {{0,-1}, {-1,0}, {1,0}}, // ㅓ모양
          {{0,-1}, {0,1}, {1,0}} //ㅜ모양
           };

void check_exception(int x,int y){
    int row_size = v.size();
    int cell_size = v[0].size();
    FOR(i,0,row_size){
        int sum = map[x][y];
        FOR(j,0,cell_size){
            pair<int,int>& current = v[i][j];
            int nx = x + current.first;
            int ny = y + current.second;
            if(is_in(nx,ny)){
                sum += map[nx][ny];
            }
        }
        if(sum > answer)
            answer = sum;
    }
}

int main(){
    cin>>n>>m;
    FOR(i,0,n)
        FOR(j,0,m)
            cin>>map[i][j];

    FOR(i,0,n){
        FOR(j,0,m){
            dfs(i,j,map[i][j],1);
            check_exception(i,j);
        }
    }

    cout<<answer<<endl;
    return 0;
}