백준 14500 (테트로미노) c++

문제

14500번: 테트로미노

n * m 의 공간은 한 칸당 1이상 1000이하의 수를 가집니다. 

이 때 다음과 같은 공간의 합의 최대를 구하는 문제입니다.

위의 공간은 n * m의 공간에서 상하좌우로 대칭이 가능합니다.

 

처음에 이 문제를 접근할 때에는 n * m 배열에서 첫번째 인덱스 부터 시작해서

위의 도형을 차례대로 대칭하면서 최댓값을 구하려 했지만 시간이 너무 많이 들고 구현에 어려움이 있었습니다.

 

하지만 자세히 도형들을 살펴보면 ㅜ 모형을 제외한 나머지 도형들은 dfs 탐색으로 깊이가 3으로 통일 됩니다.

따라서 첫번째 기준점을 잡고 깊이가 3인 dfs를 진행하면 ㅜ를 제외한 나머지 도형들에 대해서

최댓값을 알 수 있습니다.

depth가 3이되면 ans를 갱신해 줍니다.

void dfs(int x, int y, int sum, int depth) {
    visit[x][y] = true;
    if (depth == 3) {
        ans = max(ans, sum);
        return;
    }
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (visit[nx][ny])continue;
        dfs(nx, ny, sum + arr[nx][ny], depth + 1);
        visit[nx][ny] = false;
    }
}

 

이제 ㅜ 모형을 생각해 줘야 합니다.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        memset(visit, false, sizeof(visit));
        dfs(i, j, arr[i][j], 0);
        if (i - 1 >= 0 && j + 2 < m) { // ㅗ
            int temp = 0;
            temp = arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i - 1][j + 1];
            ans = max(temp, ans);
        }
        if (j + 2 < m && i + 1 < n) { //ㅜ
            int temp = 0;
            temp = arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 1];
            ans = max(temp, ans);
        }
        if (i + 2 < n && j + 1 < m) { //ㅏ
            int temp = 0;
            temp = arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 1][j + 1];
            ans = max(temp, ans);
        }
        if (i + 1 < n && i - 1 >= 0 && j + 1 < m) { //ㅓ
            int temp = 0;
            temp = arr[i][j] + arr[i - 1][j + 1] + arr[i][j + 1] + arr[i + 1][j + 1];
            ans = max(temp, ans);
        }
    }
}

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
int n, m;
int arr[501][501];
bool visit[501][501];
int ans;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1,0, -1, 0 };
void dfs(int x, int y, int sum, int cnt);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> arr[i][j];
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            memset(visit, false, sizeof(visit));
            dfs(i, j, arr[i][j], 0);
            if (i - 1 >= 0 && j + 2 < m) { // ㅗ
                int temp = 0;
                temp = arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i - 1][j + 1];
                ans = max(temp, ans);
            }
            if (j + 2 < m && i + 1 < n) { //ㅜ
                int temp = 0;
                temp = arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 1];
                ans = max(temp, ans);
            }
            if (i + 2 < n && j + 1 < m) { //ㅏ
                int temp = 0;
                temp = arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 1][j + 1];
                ans = max(temp, ans);
            }
            if (i + 1 < n && i - 1 >= 0 && j + 1 < m) { //ㅓ
                int temp = 0;
                temp = arr[i][j] + arr[i - 1][j + 1] + arr[i][j + 1] + arr[i + 1][j + 1];
                ans = max(temp, ans);
            }
        }
    }
 
    cout << ans;
    return 0;
}
void dfs(int x, int y, int sum, int depth) {
    visit[x][y] = true;
    if (depth == 3) {
        ans = max(ans, sum);
        return;
    }
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (visit[nx][ny])continue;
        dfs(nx, ny, sum + arr[nx][ny], depth + 1);
        visit[nx][ny] = false;
    }
}