[백준]14500 - 테르로미노

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

 

주어진 배열에서 위 그림과 같이 연이은 숫자 4개의 합의 최대값을 구하시오

 

-> dfs로 4칸 탐색하면 ㅗ 모양을 제외한 다른 모양은 해결된다

 

ㅗ 모양 해결법

1.가능한 경우의 수를 전부 for문으로 처리

2.2칸 탐색 중에 탐색 가능한 2칸 값 더하기

3.3칸 탐색 중에 이전 칸에서 탐색 가능한 칸 값 더하기

 

3번은 복잡할 것 같아서 생략했고

1번과 2번 방식으로 구현했는데 의외로 1번이 2번보다 빨랐다

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int map[501][501];
int c[501][501];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int k = 0;
int nn = 0;
int mm = 0;
int answer = -1;
int ct=0;
void dfs(int x, int y);
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    nn = N;
    mm = 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++) {
            k = 0;
            ct = 0;
            dfs(j, i);
            c[i][j] = 0;
        }
    }
    
    for (int i = 1; i < N-1; i++) {
        for (int j = 1; j < M-1; j++) {
            int z = 0;
            int zz = 0;
            z = map[i][j] + map[i - 1][j] + map[i + 1][j] + map[i][j + 1] + map[i][j - 1];
            zz = max({ z - map[i - 1][j], z - map[i + 1][j], z - map[i][j + 1], z - map[i][j - 1] });
            //cout << "zz=" << zz<<"\n";
            if (zz > answer)
                answer = zz;
        }
    }
    for (int i = 1; i < M - 1 ; i++) {
        int z = map[0][i] + map[0][i - 1] + map[0][i + 1] + map[1][i];
        if (z > answer)
            answer = z;
        int t = map[N-1][i] + map[N-1][i - 1] + map[N-1][i + 1] + map[N-2][i];
        if (t > answer)
            answer = t;
    }
    for (int i = 1; i < N - 1; i++) {
        int z = map[i][0] + map[i-1][0] + map[i+1][0] + map[i][1];
        if (z > answer)
            answer = z;
        int t = map[i][M-1] + map[i-1][M-1] + map[i+1][M-1] + map[i][M-2];
        if (t > answer)
            answer = t;
    }
    
    cout << answer;
}

void dfs(int x, int y) {
    k += map[y][x];
    //Sleep(1000);
   
    c[y][x] = 1;
    ct++;
    if (ct == 4) {
        if (k > answer) {
            answer = k;
            //cout << "(" << x << "," << y << ") - "<<k<<"\n";
        }
        return;
    }
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx > -1 && ny > -1 && nx < mm && ny < nn) {
            if (c[ny][nx] != 1) {
                dfs(nx, ny);
                c[ny][nx] = 0;
                ct--;
                k -= map[ny][nx];
            }
        }
    }
}

 

메인함수

-cin으로 입력 받기

-dfs 탐색

-모서리를 제외한 ㅗ 모양 탐ㅅ개

-모서리의 ㅗ 모양 탐색

 

dfs

-k(점수 합) c[](지나온 칸인지 체크) ct(지나온 칸 개수) 처리

-ct가 4이면 k 넘기기

-상하좌우 dfs 탐색

ㄴ dfs 탐색 이후 k c[] ct 다시 롤백

 

 

else if (ct == 2) {
        int v = k;
        int mini = 9999;
        int cs = 0;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx > -1 && ny > -1 && nx < mm && ny < nn) {
                if (c[ny][nx] != 1) {
                    cs++;
                    v += map[ny][nx];
                    if (map[ny][nx] < mini)
                        mini = map[ny][nx];
                }
            }
        }
        if(cs==3)
            v -= mini;
        if (cs!=1 && v > answer)
            answer = v;
    }

2번 코드

ct가 2일때 상하좌우 탐색하여 ㅗ 모양 처리