[백준/Baekjoon] 14500 테트로미노 C++ :: DFS

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

14500번: 테트로미노

 

---

 

1. Logic

 - 문제를 읽고 회전이나 대칭을 해도 된다고 쓰여있었기 때문에 재귀를 통해서 정사각형 한 칸씩 차지해 나가며 해당 칸에 있는 숫자를 더해서 Max값을 더하면 될것 같다고 생각했다.

 

- 재귀를 통해서 가기때문에 DFS로직을 생각했고 다른 모양은 다 가능 하지만 ㅗ, ㅏ, ㅜ, ㅓ 모양은 재귀를 통해서 구할 수 없기 때문에 따로 구해줘야 한다.

 

 

 

---

 

 

2. Code

 

#include<bits/stdc++.h>

using namespace std;

int n, m;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

vector<vector<int>> vec(501, vector<int>(501, 0));
vector<vector<bool>> vis(501, vector<bool>(501, false));

int DFS(int y, int x, int cnt) {
    if(cnt == 4) {
        return vec[y][x];
    }

    int sum = 0;

    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
        if(vis[ny][nx]) continue;
        vis[ny][nx] = true;
        sum = max(sum, vec[y][x] + DFS(ny, nx, cnt + 1));
        vis[ny][nx] = false;
    }

    return sum;
}

int fxxkshape(int y, int  x) {
    int ans = 0;
    
    //ㅗ
    if(x >= 1 && y >= 1 && x + 1 <= m)
        ans = max(ans, vec[y][x] + vec[y - 1][x] + vec[y][x - 1] + vec[y][x + 1]);
    //ㅏ
    if(x + 1 <= m && y + 1 <= n && y >= 1)
        ans = max(ans, vec[y][x] + vec[y - 1][x] + vec[y + 1][x] + vec[y][x + 1]);
    //ㅜ
    if(x >= 1 && y + 1 <= n && x + 1 <= m)
        ans = max(ans, vec[y][x] + vec[y][x - 1] + vec[y][x + 1] + vec[y + 1][x]);
    //ㅓ
    if(x >= 1 && y >= 1 && y + 1 <= n)
        ans = max(ans, vec[y][x] + vec[y - 1][x] + vec[y][x - 1] + vec[y + 1][x]);

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> vec[i][j];
        }
    }

    int res = 0;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            vis[i][j] = true;
            res = max(res, DFS(i, j, 1));
            res = max(res, fxxkshape(i, j));
            vis[i][j] = false;
        }
    }

    cout << res;
}

 

3. Feedback

1. vis배열을 true로 만들어 준 후 모양을 만들고 나면 다시  false 처리를 해줘야 다음 칸으로 이동해서도 해당 칸에 적합한 모양을 구할 수 있다.

 

2. 재귀로 만들지 못하는 모양은 직접 구해줘야함. 여기서 조심해야할 점은 모양이 만들어 질 수 있는 범위를 정확하게 확인하고 범위를 설정할 것.