알고리즘 문제/[백준]

백준 14500 테트로미오

latter2005 2020. 10. 30. 15:13

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

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변

www.acmicpc.net

문제 확인

 

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

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

 

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

 

풀이

 

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

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

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

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

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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, -11, ary[i][j]);
            ex(i, j++);
        }
    printf("%d", res);
 
}
cs

 

반응형

'알고리즘 문제 > [백준]' 카테고리의 다른 글

[백준] 16235번 나무 재테크  (0) 2020.11.02
백준 16637 괄호 추가하기  (0) 2020.10.30
백준 15684 사다리조작  (0) 2020.10.30
백준 12094: 2048(Hard)  (0) 2020.10.30
백준 16234번: 인구이동  (0) 2020.10.29