[Algorithm] 백준 14500 테트로미노 - C++, DFS

14500번: 테트로미노

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX = 501;
int n, m;
int map[MAX][MAX];
bool visit[MAX][MAX];
int moveX[] = { 0, 0, 1, -1 };
int moveY[] = { 1, -1, 0, 0 };
int answer = -1;

bool IsOut(int y, int x){
    return (y < 0 || x < 0 || y >= n || x >= m) ? true : false;
}

void GetSumFrom(int y, int x, int count, int sum){
    if(count == 4){
        answer = max(answer, sum);
        return;
    }

    for(int i = 0; i < 4; i++){
        int nextY = y + moveY[i];
        int nextX = x + moveX[i];

        if(IsOut(nextY, nextX)) continue;
        if(visit[nextY][nextX]) continue;

        visit[nextY][nextX] = true;
        GetSumFrom(nextY, nextX, count + 1, sum + map[nextY][nextX]);
        GetSumFrom(y, x, count + 1, sum + map[nextY][nextX]);
        visit[nextY][nextX] = false;
    }
}


int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // input
    cin >> n >> m;
    for(int y = 0; y < n; y++){
        for(int x = 0; x < m; x++){
            cin >> map[y][x];
        }
    }

    // solve
    for(int y = 0; y < n; y++){
        for(int x = 0; x < m; x++){
            visit[y][x] = true;
            GetSumFrom(y, x, 1, map[y][x]);
            visit[y][x] = false;
        }
    }

    // print
    cout << answer << '\n';
}

---

 사실 어디 코테와 비슷한 문제인데...1 X 1 블럭을 4개 이어서 만드는건데 이 경우 DFS를 이런 식으로 변형을 하면 코드를 짧게 가져올 수 있습니다. (물론 비교해보니 시간은 더 오래 걸리는 방법입니다.)

        GetSumFrom(nextY, nextX, count + 1, sum + map[nextY][nextX]);
        GetSumFrom(y, x, count + 1, sum + map[nextY][nextX]);

아래 인라로 y, x 를 넣은게 ㅗ, ㅓ, ㅜ, ㅏ를 위한 함수인데 논리적으로 보면 다음 칸에 방문을 했다가 바로 돌아온 모양이 되는 것입니다.

O	X	X
O*	X	X
X	X	X

위 상태에서 *가 현재 커서라고 하면 위에 y, x 인자를 넣는다면

O	X	X
O*	O	X
X	X	X

이런 모양이 되는 것이조. 1, 1을 잡았는데 커서는 이전에 그대로 있는 것입니다. 그러면 주변에 남은 칸으로 가서 ㅗ, ㅓ, ㅏ, ㅜ 중 모양이 하나 나오게 되겠죠.