문제 주소 : 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, -1, 1, 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 |