백준 14500 테트로미오

문제 주소 : www.acmicpc.net/problem/14500

14500번: 테트로미노

문제 확인

 

간단하게 dfs 그래프 탐색으로 해결할 수 있는 문제

아래 그림과 같이 최대 4번의 깊이 탐색으로 해결 할 수 있습니다. 

 

ㅜ 형태의 모양은 dfs를 통해 탐색하기 까다로우므로 따로 함수를 만들어 탐색하도록 합니다.

 

풀이

 

처음 배열을 초기화 할 때 최대값을 미리 저장해두고 탐색 시 기대값 계산에 사용합니다. 이를 통하여 가지치기를 진행합니다.

탐색 시 이전 방향으로 돌아가는 것을 막기 위해 다음 노드 탐색 시 이동한 방향을 같이 넘겨줍니다.

탐색 최대 횟수는 4번이므로 돌아가는 방향만 제거하면 굳이 visited 배열을 사용할 필요 없습니다

ㅜ 형태 모양은 다른 함수에서 확인하며 방향 변환 배열 뒤에 추가로 덧붙여 인덱스 넘어가는 상황을 방지합니다

 

코드

#include <cstdio>
 
class fast_io { //빠른 입력
public:
    int next_int() {
        int x = 0;
        bool neg = false;
        register int c;
        c = getchar_unlocked();
        if (c == '-') {
            neg = true;
            c = getchar();
        }
        for (; (c > 47 && c < 58); c = getchar_unlocked())
            x = (x << 1) + (x << 3) + c - 48;
        if (neg)
            x *= -1;
        return x;
    }
};
fast_io fio;
short dx[] = { 0,0,-1,1,0,0 },
dy[] = { 1,-1,0,0,1,-1 }; // 동서북남 동서 : ㅜ 모양 탐색 시 배열 인덱스 넘어가는것 방지
short ary[502][502];
int res, max;
void dfs(int x, int y, int b, int cnt, int val) {
    if (cnt == 4) {
        if (res < val)
            res = val;
        return;
    }
    if (res > (4 - cnt) * max + val)//기대값 보다 현재 최대값이 작다면 탐색 종료
        return;
    for (int i = 0; i < 4; i++) {
        if (b == i) continue;//돌아가는 방향
        int nx = x + dx[i], ny = y + dy[i];
        if (ary[nx][ny] != 0)
            dfs(nx, ny, i ^ 1, cnt + 1, val + ary[nx][ny]);//0^1 = 1, 1^1 = 0, 2^1 = 3, 3^1 = 2
    }
}
inline void ex(int x, int y) {//dfs로는 불가능한 ㅗ 모양
    if (res > 3 * max + ary[x][y]) return;
    int tmp;
    for (int i = 0; i < 4; i++) {
        tmp = ary[x][y] + ary[dx[i] + x][dy[i] + y] + ary[dx[i + 1] + x][dy[i + 1] + y] + ary[dx[i + 2] + x][dy[i + 2] + y];
        if (tmp > res)
            res = tmp;
    }
}
int main() {
    int n = fio.next_int(), m = fio.next_int();
    for (int i = 1, j = 1; i <= n; i++, j = 1)
        while (j <= m) {
            ary[i][j] = fio.next_int();
            if (ary[i][j] > max)//최대값
                max = ary[i][j];
            j++;
        }
    for (int i = 1, j = 1; i <= n; i++, j = 0)
        while (j <= m) {
            dfs(i, j, -1, 1, ary[i][j]);
            ex(i, j++);
        }
    printf("%d", res);
 
}