[백준] 14500번: 테트로미노

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

14500번: 테트로미노

문제 확인

 

모든 루프를 제거하고 조건식으로 풀 수 있는 문제이지만 이는 너무 시간이 많이 드는 작업이라 간단하게 dfs와 가지치기를 통해 풀었습니다. 조건식 풀이로 푼다면 시간과 메모리 모두 단축할 수 있습니다.

테트로미노는 최대 4개까지의 도형이므로 탐색이 깊지 않으므로 dfs로 풀어도 무방합니다.

주의해야 할 점은 다른 4가지의 테트로미노는 dfs로 풀 수 있지만 ㅜ 모양의 테트로미노는 dfs를 통해 구현할 수 없으므로 따로 작업을 해 주어야 합니다.

 

풀이

 

배열에 값을 입력받을 시 가지치기를 위한 최댓값을 미리 기록 해 둡니다.

후 dfs를 통해 탐색하여 최댓값을 찾습니다. 이때 최대 탐색 깊이가 4이므로 그전에 탐색했던 칸으로 돌아가지만 않으면

visited 배열을 사용하지 않고 잘못된 탐색을 배제할 수 있습니다. 이는 xor을 통해 전의 방향과 비교하여 구형하였습니다.

최댓값을 통해 남은 횟수 * max 값을 이용하여 현재까지의 최댓값을 넘지 못한다면 탐색을 종료하여 탐색 횟수를 줄일 수 있습니다.

ㅜ 모양의 테트로미노는 따로 함수를 두어 구합니다.

 

코드

#include <cstdio>
 
#include <unistd.h>
namespace io {
    const signed IS = 1 << 13, OS = 1 << 20;
    char I[IS + 1], *J = I;
    //char O[OS], *K = O;
 
    inline void daer() { if (J >= I + IS - 64) { char*p = I; do*p++ = *J++; while (J != I + IS); p[read(0, p, I + IS - p)] = 0; J = I; } }
    template<int N = 10, typename T = int> inline T getu() { daer(); T x = 0; int k = 0; do x = x * 10 + *J - '0'; while (*++J >= '0'&&++k < N); ++J; return x; }
    template<int N = 10, typename T = int>inline  T geti() { daer(); bool e = *J == '-'; J += e; return(e ? -1 : 1)*getu<N, T>(); }
    /*inline void flush() { write(1, O, K - O); K = O; }
    template<int N = 10, typename T = int> inline void putu(T n) { char s[(N + 7) / 8 * 8], *p = s; int k = 0; do*p++ = n % 10 + 48; while ((n /= 10) && ++k < N); do*K++ = *--p; while (p != s); *K++ = 10; if (K >= O + OS - 64)flush(); }
    template<int N = 10, typename T = int> inline void puti(T n) { if (n < 0)*K++ = '-', n = -n; putu<N, T>(n); }*/
    struct f { f() { I[read(0, I, IS)] = 0; }~f() { /*flush();*/ } }flu;
};//출처 : https://cgiosy.github.io/posts/fast-io
using namespace io;
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]);
    }
}
inline void ex(int x, int y) {
    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 = getu(), m = getu();
    for (int i = 1, j = 1; i <= n; i++, j = 1)
        while (j <= m) {
            ary[i][j] = getu();
            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);
 
}