백준 14500. 테트로미노
알고리즘 기초 문제 중 브루트포스 기초 문제(500)
1. 간단 설명
NxM 맵에 각 칸에 정수가 하나씩 쓰여져있다
테트로미노 하나를 놓아서, 그 테트로미노가 놓인 칸에 쓰여있는 수들의 합이 최대가 되는 경우를 구하는 문제
2. 예시
1
2
3
4
5
6
7
8
9
10
5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1
에서는
4 5 6
4
를 고르는 경우가 19로 가장 크다
이런식으로 블록을 놓아서 가장 큰 합을 찾는 문제
3. 알고리즘
직접 테트로미노를 만들고, 대칭 회전시켜서
이 테트로미노가 밟는 칸의 숫자를 모두 더한다
DFS로도 풀 수 있지만, T 모양은 별도로 처리해주어야하기 때문에
간단히 모든 모양을 직접 구현하여 풀었다
막대기와 같은 테트로미노는 회전하나 대칭하나 같기 때문에
40(5개 * 대칭 2개 * 회전 4개)개의 테트로미노를 모두 구현할 필요 없이, 총 19개만 구현하면 된다
- N과 M을 입력받는다
- 최대값을 0으로 초기화
- 0,0부터 시작하여 각 칸에 19개의 테트로미노를 하나씩 놓아본다
- 해당 칸의 숫자를 더한 수가 최대값이라면 갱신함
- 최대값 출력 후 종료
4. 소스코드
블럭의 좌표를 기록하는 방식
이 방식이 메모리 효율 및 성능적에서 낫다
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
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
using namespace std;
int n, m;
int map[501][501];
// 19개 블록에 대해 y,x 좌표를 저장
// 회전 및 대칭에 대해 중복은 제거
int tetrominon[19][4][2] = {
// 막대(2개)
{ {0,0}, {0,1}, {0,2}, {0,3} },
{ {0,0}, {1,0}, {2,0}, {3,0} },
// 네모
{ {0,0}, {0,1}, {1,0}, {1,1} },
// L
{ {0,0}, {1,0}, {1,1}, {1,2} },
{ {0,0}, {0,1}, {1,0}, {2,0} },
{ {0,0}, {0,1}, {0,2}, {1,2} },
{ {0,0}, {1,0}, {2,0}, {2,-1} },
{ {0,0}, {0,1}, {0,2}, {-1,2} },
{ {0,0}, {1,0}, {2,0}, {2,1} },
{ {0,0}, {0,1}, {0,2}, {1,0} },
{ {0,0}, {0,1}, {1,1}, {2,1} },
// Z
{ {0,0}, {0,1}, {-1,1}, {-1,2} },
{ {0,0}, {1,0}, {1,1}, {2,1} },
{ {0,0}, {0,1}, {1,1}, {1,2} },
{ {0,0}, {1,0}, {1,-1}, {2,-1} },
// T
{ {0,0}, {0,1}, {0,2}, {-1,1} },
{ {0,0}, {0,1}, {0,2}, {1,1} },
{ {0,0}, {1,0}, {2,0}, {1,1} },
{ {0,0}, {1,0}, {2,0}, {1,-1} },
};
void Input() {
cin >> n >> m;
for (int y = 0; y < n; y++) {
for (int x = 0; x < m; x++) {
cin >> map[y][x];
}
}
}
int main() {
// freopen_s(new FILE*, "test.txt", "r", stdin);
Input();
// 값 찾기
int max_value = 0;
for (int y = 0; y < n; y++) {
for (int x = 0; x < m; x++) {
// 블럭 19개에 대해 확인
for (int i = 0; i < 19; i++) {
int sum = 0;
for (int j = 0; j < 4; j++) { // 블럭은 4칸
int dy = y + tetrominon[i][j][0];
int dx = x + tetrominon[i][j][1];
if (dy < 0 || dx < 0 || dy >= n || dx >= m) continue; // 하나라도 밖으로 튀어나가면 정지
sum += map[dy][dx];
}
if (sum > max_value) {
max_value = sum;
}
}
}
}
cout << max_value;
return 0;
}
블럭을 시각화하기 위해 3차원 배열로 놓은 방식
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <iostream>
#include <algorithm>
#define BLOCK 19
using namespace std;
int tetromino[BLOCK][4][4] = {
// 막대기
{
1,1,1,1,
0,0,0,0,
0,0,0,0,
0,0,0,0
},
{
1,0,0,0,
1,0,0,0,
1,0,0,0,
1,0,0,0,
},
// 네모
{
1,1,0,0,
1,1,0,0,
0,0,0,0,
0,0,0,0,
},
// L
{
1,1,1,0,
1,0,0,0,
0,0,0,0,
0,0,0,0
},
{
1,1,0,0,
0,1,0,0,
0,1,0,0,
0,0,0,0
},
{
0,0,1,0,
1,1,1,0,
0,0,0,0,
0,0,0,0
},
{
1,0,0,0,
1,0,0,0,
1,1,0,0,
0,0,0,0
},
// L 대칭
{
1,1,0,0,
1,0,0,0,
1,0,0,0,
0,0,0,0
},
{
1,0,0,0,
1,1,1,0,
0,0,0,0,
0,0,0,0
},
{
0,1,0,0,
0,1,0,0,
1,1,0,0,
0,0,0,0
},
{
1,1,1,0,
0,0,1,0,
0,0,0,0,
0,0,0,0
},
// S
{
1,0,0,0,
1,1,0,0,
0,1,0,0,
0,0,0,0
},
{
0,1,1,0,
1,1,0,0,
0,0,0,0,
0,0,0,0
},
// S 대칭
{
1,1,0,0,
0,1,1,0,
0,0,0,0,
0,0,0,0
},
{
0,1,0,0,
1,1,0,0,
1,0,0,0,
0,0,0,0
},
// T
{
1,1,1,0,
0,1,0,0,
0,0,0,0,
0,0,0,0
},
{
0,1,0,0,
1,1,0,0,
0,1,0,0,
0,0,0,0
},
{
0,1,0,0,
1,1,1,0,
0,0,0,0,
0,0,0,0
},
{
1,0,0,0,
1,1,0,0,
1,0,0,0,
0,0,0,0
}
};
int N, M;
int map[510][510];
int main() {
freopen_s(new FILE*, "input.txt", "r", stdin);
cin >> N >> M;
for (int y = 0; y < N; y++) {
for (int x = 0; x < M; x++) {
cin >> map[y][x];
}
}
int max_val = 0;
for (int y = 0; y < N; y++) {
for (int x = 0; x < M; x++) {
for (int k = 0; k < BLOCK; k++) {
int cur = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (tetromino[k][i][j] != 0) {
cur += map[y + i][x + j];
}
}
}
max_val = max(max_val, cur);
}
}
}
cout << max_val;
return 0;
}
추가
브루트포스를 복습하면서 다시 풀어보았는데
테트로미노를 19개 만드는 과정에서 실수가 있었다
기존에는
{ {0,0}, {0,1}, {0,2}, {-1,2} }
이런식으로 {0,0}을 원점으로 두고,
-1과 같이 왼쪽으로도 이동하는 방식을 사용했다면
이번에는 {0,0}을 비워두고
{ {0,1}, {1,1}, {2,0}, {2,1} },과 같이 원점을 이동하는 방식을 사용했다
그러나 이런 방식은 원점 때문에 문제가 발생할 수 있다
y, x 좌표에서 19개의 테트로미노를 놓는 방식을 사용하고 있는데
(2,4)에 { {0,2}, {1,0}, {1,1}, {1,2}} 테트로미노를 놓는다고 하면,
(2,4)에서 시작하여 각 블록의 좌표를 더하면, (2,6), (3,4), (3,5), (3,6)의 위치에 블록이 배치됨
맵의 크기는 5x5이므로, (2,6)과 (3,6) 좌표는 맵을 벗어남
코드에서는 경계를 벗어나는 (2,6)과 (3,6) 좌표를 무시하고, 나머지 블록만 합산
따라서 전체 테트로미노의 블록이 아닌 일부만 합산되므로, 이로 인해 잘못된 합계가 계산된다
그러므로, 오프셋을 통해 모든 테트로미노의 시작점을 맞춰줘야 한다