14500번-테트로미노

문제

https://www.acmicpc.net/status?user_id=skaguq4270&problem_id=14500&from_mine=1 

채점 현황

---

접근방법

1) 접근 사고

문제에 보면 한 테트로미노가 가질수 있는 최대값을 물어보는 문제였습니다.

도형들의 길이가 4이기 때문에 각 좌표마다 DFS탐색을 통해 4번째 탐색이 되었을때의 합계의 값을 최대가 되게 비교해주면 되는 방법으로 해결하였습니다.  이 방법으로 문제를 해결하면 예외가 한 가지 존재하는데 'ㅗ' 도형일 경우 DFS 탐색을 통해 모든 경우를 탐색하는게 불가능합니다. 왜냐하면 튀어나온 부분으로 들어갔다가 다시 돌아와서 탐색이 DFS로는 불가능하기 때문입니다. 이 부분만 저는 따로 함수를 구현해서 예외처리 해주었습니다. 

2) 시간 복잡도

O(n^2)의 시간복잡도로 해결

3) 배운 점

인덱스 초과 부분은 먼저 범위를 적어놓고 조건을 적어주는게 더 편하다.(ex:) subSearch 함수의 if문들)

4) PS

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
 
const int MAX = 505;
int board[MAX][MAX];
int n, m;
int ret;
int moveY[] = {-1,1,0,0};
int moveX[] = {0,0,-1,1};
bool visited[MAX][MAX];
 
bool isValid(int y, int x){
    return (y < 0 || y >= n || x < 0 || x >= m);
}
 
int main(void)
{
    fastio;
    cin >> n >> m;
 
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> board[i][j];
        }
    }
 
    auto DFS = [&](int level, int y, int x, auto &&DFS) -> int{
        if(level == 4){
            return board[y][x];
        }
 
        int sum = 0;
        for(int d = 0; d < 4; d++){
            int ny = y + moveY[d];
            int nx = x + moveX[d];
 
            if(!isValid(ny, nx))
            if(!visited[ny][nx]){
            visited[ny][nx] = true;
            sum = max(sum, board[y][x] + DFS(level + 1, ny, nx, DFS));
            visited[ny][nx] = false;
            }
        }
        return sum;
    };
 
    /*
     *  ㅁ      ㅁ
     * ㅁㅁㅁ   ㅁㅁ
     *          ㅁ
     * ㅁ
     * ㅁㅁ    ㅁㅁㅁ
     * ㅁ       ㅁ
     */
    auto subSearch = [&](int y , int x) -> int{
        int ret = 0;
        if (y - 1 >= 0 && 0 <= x - 1 && x + 1 < m)
            ret = max(ret, board[y][x] + board[y - 1][x] + board[y][x - 1] + board[y][x + 1]);
        if (x - 1>= 0 && y - 1>= 0 && y + 1 < n)
            ret = max(ret, board[y][x] + board[y - 1][x] + board[y + 1][x] + board[y][x - 1]);
        if (y - 1 >= 0 && y + 1< n && x + 1 < m)
            ret = max(ret, board[y][x] + board[y - 1][x] + board[y + 1][x] + board[y][x + 1]);
        if (x - 1 >= 0 && x + 1 < m && y + 1 < n)
            ret = max(ret, board[y][x] + board[y][x - 1] + board[y][x + 1] + board[y + 1][x]);
        return ret;
    };
 
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            visited[i][j] = true;
            ret = max(ret,DFS(1, i, j, DFS));
            ret = max(ret, subSearch(i, j));
            visited[i][j] = false;
        }
    }
 
    cout << ret <<"\n";
}