백준 14500번 : 테트로미노

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

14500번: 테트로미노

 

 알고리즘 

 

1. 테트로 미노중 'ㅏ' 모양을 제외하고는 깊이 4인 dfs나 bfs 로 표현가능하므로 'ㅏ' 모양을 제외하고

   그래프 탐색 알고 리즘으로 구현 하여 칸의 최댓값을 구한다.

2. 'ㅏ' 형태의 테트로미노만 따로 함수를 만들어 칸의 최댓값을 구한다.

3. 최댓값 출력 .

 

 코드 

 

#include<iostream>
#include<algorithm>
using namespace std;
 
int N, M;
int map[510][510];
int visited[510][510];
int max_sum = 0;
int result = 0;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
void dfs(int, int, int, int);
int another(int, int);
 
 
int main() {
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
 
 
            visited[i][j] = 1;
 
            //깊이 4인 테트로미노를 이용해 최댓값 갱신
            dfs(i, j, 0, map[i][j]);
            result = max(result, max_sum);
 
            //'ㅏ' 모양의 테토르미노를 이용해 최댓값 갱신
            result = max(result, another(i, j));
 
            //백트래킹
            visited[i][j] = 0;
        }
    }
    cout << result;
}
 
void dfs(int y, int x, int cnt, int sum) {
 
 
    //깊이가 4이면 최댓값 갱신후 return
    if (cnt == 3) {
        max_sum = max(max_sum, sum);
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        int next_y = y + dy[i];
        int next_x = x + dx[i];
 
        if (next_y >= 0 && next_y < N && next_x >= 0 && next_x < M) {
 
            if (!visited[next_y][next_x]) {
 
                visited[next_y][next_x] = 1;
                dfs(next_y, next_x, cnt + 1, sum + map[next_y][next_x]);
                //백트래킹
                visited[next_y][next_x] = 0;
            }
        }
    }
}
 
int another(int y, int x) {
    int num = 0;
 
    // 'ㅗ' 모양의 테트로미노
    if (y > 0 && x > 0 && x < M - 1) {
        num = max(num, map[y][x] + map[y - 1][x] + map[y][x + 1] + map[y][x - 1]);
    }
 
    // 'ㅏ' 모양의 테트로미노
    if (y > 0 && y < N - 1 && x < M - 1) {
        num = max(num, map[y][x] + map[y - 1][x] + map[y][x + 1] + map[y + 1][x]);
    }
 
    // 'ㅜ' 모양의 테트로미노
    if (y < N - 1 && x > 0 && x < M - 1) {
        num = max(num, map[y][x] + map[y + 1][x] + map[y][x + 1] + map[y][x - 1]);
    }
 
    // 'ㅓ' 모양의 테트로미노
    if (y > 0 && x > 0 && y < N - 1) {
        num = max(num, map[y][x] + map[y - 1][x] + map[y + 1][x] + map[y][x - 1]);
    }
    return num;
}