백준 14500: 테트로미노

문제

문제 링크: https://www.acmicpc.net/problem/14500

DFS로 문제를 푸는 것은 인지를 하였으나, 직접적으로 코딩을 하지는 못하였습니다.

오늘도 많은 부족함을 느끼는 날입니다. 열심히 하다보면 자연히 늘겠죠...?

문제에 대해 검색해보니 많은 분들이 DFS를 사용하여 풀었습니다. 

혹시 문제를 보고 바로 오...하나가 이상하네? 라고 찾으신 분은 DFS에 대해서 정확히 이해 하셨을꺼라 생각됩니다.

저는 검색을 하고나서야 알게 되었네요...ㅎㅎㅎ;; 

ㅗ 모양은 DFS로 탐색이 불가능합니다. 따라서 ㅗ 모양만 다른 방법으로 찾아야합니다.

살짝 문제를 꼬아낸것 같습니다.

도형을 탐색 하면서 해당 칸의 수를 더해가면서 최댓값을 구하면 되는 문제였습니다.

찾아보면 또..은근 쉬워 보입니다...

코드

#include <cstdio>
#include <algorithm>
using namespace std;
 
int board[500][500];
bool visit[500][500];
 
int n,m;
 
int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};
 
//DFS를 할 수 있는 경우의 도형들
int tetromino(int x, int y, int cnt){
    if(cnt >= 5){
        return 0;
    }
    int ans = 0;
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(0<=nx && nx<n && 0<=ny && ny<m){
            if(visit[nx][ny] == false){
                visit[nx][ny] = true;
                ans= max( ans, tetromino(nx, ny, cnt+1)+ board[x][y] );
                visit[nx][ny] = false;
            }
        }
    }
    return ans;
}
//ㅗ모양은 DFS를 사용할 수 없으므로 따로 구해준다.
int exShape(int x, int y){
    int ans = 0;
    // ㅗ모양
    if(x>=1 && y>=1 && y<m-1)
        ans = max(ans, board[x][y]+board[x-1][y]+board[x][y-1]+board[x][y+1]);
    // ㅜ모양
    if(x<n-1 && y>=1 && y<m-1)
        ans = max(ans, board[x][y]+board[x+1][y]+board[x][y-1]+board[x][y+1]);
    // ㅏ모양
    if(x<n-1 && x>=1 && y<m-1)
        ans = max(ans, board[x][y]+board[x+1][y]+board[x-1][y]+board[x][y+1]);
    // ㅓ모양
    if(x<n-1 && x>=1 && y>=1)
        ans = max(ans, board[x][y]+board[x+1][y]+board[x-1][y]+board[x][y-1]);
    return ans;
}
int main(){
    scanf("%d %d", &n, &m);
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            scanf("%d", &board[i][j]);
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            visit[i][j] = true;
            ans = max(ans, exShape(i, j));
            ans = max(ans, tetromino(i, j, 1));
            visit[i][j] = false;
        }
    }
    
    printf("%d\n",ans);
    return 0;
}