[BOJ] 14500. 테트로미노

[문제]

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

14500번: 테트로미노

[풀이]

 

14500

맞았습니다!!

3212 kb

252 ms

C++14 / 수정

1593B

1일 전

 

1) 좌표를 상하좌우로 탐색하여 정사각형 4개로 이루어진 테트로미노를 만든다. 

 

2) 테트로미노를 이루는 정사각형에 적힌 값의 합 중 큰 값을 구해야 한다. 

 

3) ㅓ ㅗ ㅏ ㅜ 는 dfs 탐색으로 찾을 수 없다. 따라서 dfs 탐색후 별개로  十 는 구할 수 있기 때문에 十를 구한 후 최소값을 빼서 구한다. 

(dfs는 정석으로 돌린다. cnt(테트로미노를 이루는 정사각형의 개수)가 4개가 되면 최대값을 구하고 return. )

 

4) ㅓ ㅗ ㅏ ㅜ 를 구할 때 wing이 3개 이상이어야 한다. 4개일 때만 최소값을 빼준다. (맵의 가장자리에 놓인 테트로미노의 경우 wing이 4개가 될 수 없기 때문에)

 

5) 백트래킹을 사용하여 이미 방문한 노드가 배제되지 않도록 한다. 

 

* findThreeDimension() -> ㅓ ㅗ ㅏ ㅜ 를 탐색 

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
//풀이 16분 
 
int n, m, map[501][501], max_sum = 0;
bool visited[501][501];
 
int dx[4] = {0,0,-1,1}, dy[4] = {-1,1,0,0};
 
void findThreeWings(int x, int y) {
    int wings = 4, res = 0;
    vector<int> tet;
 
    //하나씩 제외될 때마다 한 개씩 줄여주고 만약 wing이 2가 되면 ㅗ ㅏ ㅜ ㅓ 가 완성될 수 없기 때문에 반환한다. 
    //ㅗ ㅏ ㅜ ㅓ 는 한쪽 날개가 범위를 벗어나거나, 4개인데 가장 최소값인 칸을 제외했을 때 만들어질 수 있다. 
    for (int i = 0; i < 4; i++) {
 
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
            wings--;
            continue;
        }
        tet.push_back(map[nx][ny]);
 
    }
    if (wings == 2 ) return;
    
    if (wings == 4) {
        //최소값을 뺀다. 
        sort(tet.begin(), tet.end());
 
        for (int i = 1; i < tet.size(); i++) {
            res += tet[i];
        }
        res += map[x][y];
    } 
    else if (wings == 3) {
        for (int i = 0; i < tet.size(); i++) {
            res += tet[i];
        }
        res += map[x][y];
    }
 
    max_sum = max(res, max_sum);
 
}
void dfs(int x, int y, int sum, int cnt) {
    visited[x][y] = true;
    if (cnt == 4) {
        //4개 다 고름 
        max_sum = max(max_sum, sum);
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
 
        if (visited[nx][ny]) continue;
 
        visited[nx][ny] = true;
        dfs(nx, ny, sum + map[nx][ny], cnt+1);
        visited[nx][ny] = false;
    }
 
    visited[x][y] = false;
}
int main() {
    ios_base:: sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j= 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
    //input 
 
    for (int i = 0; i < n; i++) {
        for (int j= 0; j < m; j++) {
            dfs(i, j, map[i][j],  1);
 
            findThreeWings(i, j); //ㅜ, ㅓ, ㅗ, ㅏ 와 같이 세 날개를 가지고 있는 테트로미노도 처리한다. 
        }
    }
 
    cout << max_sum << '\n';
 
    return 0;
 
}