포스트

BOJ 14500. 테트로미노

Problem Solving
게시
By August
좋아요 조회 11 분읽는 시간
  • 문제링크 : https://www.acmicpc.net/problem/14500

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

  • 정사각형은 서로 겹치면 안 된다.
  • 도형은 모두 연결되어 있어야 한다.
  • 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
  • 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

1. 문제해석

우선, 주어진 테트로미노를 회전, 대칭하여 만들 수 있는 테트로미노는 1+2+4+4+8=19로 총 19개이다.

그러면 한 개씩 종이 칸에 테트로미노를 하나씩 놓아보면서 합이 가장 큰 것을 구하기 위해서는 브루트 포스로 하나씩 다 맵핑해 보아야 한다. 아래와 같은 경우에 시간 복잡도는 가로가 N, 세로가 M이라고 하면 (N-3)x(M-3)이지만 N,M이 커지면 O(NxM)이 된다. 19개를 모두 해 보아야 하므로, 19xNxM이지만 19는 N과 M에 비해 매우 작기때문에 총 시간복잡도는 O(NxM)이다.

여기서 N과 M은 500을 넘지 않으므로, 충분한 시간안에 브루트 포스로 풀이가 가능하다.


<hr />

2. 문제 풀이

19개의 각 테트로미노의 모양은 고정이므로 직접 다 입력해주는 방법으로 구현한다. 그리고 정수가 쓰여진 맵을 이차원 배열로 받아서, 범위를 넘지않도록 맵핑하고 반복하면서 최댓값을 찾는다. 각 테트로미노에 따라 범위 제한은 달라질 것이다. 위의 그림처럼 검은색 점 부분만 반복하면 된다고 생각할 수 있다.

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

#include <iostream>
using namespace std;

int map[1000][1000];

int main(){
    int N,M;
    cin >> N >> M;
    int answer=0;
    
    for(int i=0;i<N;++i){
        for(int j=0;j<M;++j){
            cin >> map[i][j];
        }
    }    
    for(int i=0;i<N;++i){ // type 1
        for(int j=0;j<M-3;++j){
            if(map[i][j]+map[i][j+1]+map[i][j+2]+map[i][j+3] > answer)
                answer=map[i][j]+map[i][j+1]+map[i][j+2]+map[i][j+3];
        }
    }
    for(int i=0;i<N-3;++i){
        for(int j=0;j<M;++j){
            if(map[i][j]+map[i+1][j]+map[i+2][j]+map[i+3][j] > answer)
                answer=map[i][j]+map[i+1][j]+map[i+2][j]+map[i+3][j];
        }
    }    
    for(int i=0;i<N-1;++i){ // type 2
        for(int j=0;j<M-1;++j){
            if(map[i][j]+map[i][j+1]+map[i+1][j]+map[i+1][j+1] > answer)
                answer=map[i][j]+map[i][j+1]+map[i+1][j]+map[i+1][j+1];
        }
    }
    
    for(int i=0;i<N-2;++i){ // type 3
        for(int j=0;j<M-1;++j){
            if(map[i][j]+map[i+1][j]+map[i+2][j]+map[i+2][j+1] > answer)
                answer=map[i][j]+map[i+1][j]+map[i+2][j]+map[i+2][j+1];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i][j]+map[i+1][j]+map[i][j+1]+map[i][j+2] > answer)
                answer=map[i][j]+map[i+1][j]+map[i][j+1]+map[i][j+2];
        }
    }
    for(int i=0;i<N-2;++i){
        for(int j=0;j<M-1;++j){
            if(map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i+2][j+1] > answer)
                answer=map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i+2][j+1];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i+1][j]+map[i+1][j+1]+map[i+1][j+2]+map[i][j+2] > answer)
                answer=map[i+1][j]+map[i+1][j+1]+map[i+1][j+2]+map[i][j+2];
        }
    }
    for(int i=0;i<N-2;++i){ // type 3 - symmatric
        for(int j=0;j<M-1;++j){
            if(map[i][j+1]+map[i+1][j+1]+map[i+2][j+1]+map[i+2][j] > answer)
                answer=map[i][j+1]+map[i+1][j+1]+map[i+2][j+1]+map[i+2][j];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i][j]+map[i+1][j]+map[i+1][j+1]+map[i+1][j+2] > answer)
                answer=map[i][j]+map[i+1][j]+map[i+1][j+1]+map[i+1][j+2];
        }
    }
    for(int i=0;i<N-2;++i){
        for(int j=0;j<M-1;++j){
            if(map[i][j]+map[i+1][j]+map[i+2][j]+map[i][j+1] > answer)
                answer=map[i][j]+map[i+1][j]+map[i+2][j]+map[i][j+1];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i][j]+map[i][j+1]+map[i][j+2]+map[i+1][j+2] > answer)
                answer=map[i][j]+map[i][j+1]+map[i][j+2]+map[i+1][j+2];
        }
    }    
    for(int i=0;i<N-2;++i){ // type 4
        for(int j=0;j<M-1;++j){
            if(map[i][j]+map[i+1][j]+map[i+1][j+1]+map[i+2][j+1] > answer)
                answer=map[i][j]+map[i+1][j]+map[i+1][j+1]+map[i+2][j+1];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i][j+1]+map[i][j+2]+map[i+1][j]+map[i+1][j+1] > answer)
                answer=map[i][j+1]+map[i][j+2]+map[i+1][j]+map[i+1][j+1];
        }
    }
    for(int i=0;i<N-2;++i){
        for(int j=0;j<M-1;++j){
            if(map[i+1][j]+map[i+2][j]+map[i][j+1]+map[i+1][j+1] > answer)
                answer=map[i+1][j]+map[i+2][j]+map[i][j+1]+map[i+1][j+1];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i+1][j+2] > answer)
                answer=map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i+1][j+2];
        }
    }    
    for(int i=0;i<N-1;++i){ // type 5
        for(int j=0;j<M-2;++j){
            if(map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i][j+2] > answer)
                answer=map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i][j+2];
        }
    }
    for(int i=0;i<N-2;++i){
        for(int j=0;j<M-1;++j){
            if(map[i+1][j]+map[i][j+1]+map[i+1][j+1]+map[i+2][j+1] > answer)
                answer=map[i+1][j]+map[i][j+1]+map[i+1][j+1]+map[i+2][j+1];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i+1][j]+map[i+1][j+1]+map[i][j+1]+map[i+1][j+2] > answer)
                answer=map[i+1][j]+map[i+1][j+1]+map[i][j+1]+map[i+1][j+2];
        }
    }
    for(int i=0;i<N-2;++i){
        for(int j=0;j<M-1;++j){
            if(map[i][j]+map[i+1][j]+map[i+2][j]+map[i+1][j+1] > answer)
                answer=map[i][j]+map[i+1][j]+map[i+2][j]+map[i+1][j+1];
        }
    }
    cout << answer << "\n";
    return 0;
}

처음에는 위와 같이 반복문에서 반복횟수를 제한함으로써 범위를 제한했다. 하지만 이러한 방법으로는 실수가 너무 잦았고, 코드가 길어지는 불편함이 있었다.

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

#include <iostream>
using namespace std;
int a[500][500];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (j+3 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i][j+3];
                if (ans < temp) ans = temp;
            }
            if (i+3 < n) {
                int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+3][j];
                if (ans < temp) ans = temp;
            }
            if (i+1 < n && j+2 < m) {
                int temp = a[i][j] + a[i+1][j] + a[i+1][j+1] + a[i+1][j+2];
                if (ans < temp) ans = temp;
            }
            if (i+2 < n && j+1 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i+1][j] + a[i+2][j];
                if (ans < temp) ans = temp;
            }
            if (i+1 < n && j+2 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i+1][j+2];
                if (ans < temp) ans = temp;
            }
            if (i+2 < n && j-1 >= 0) {
                int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+2][j-1];
                if (ans < temp) ans = temp;
            }
            if (i-1 >= 0 && j+2 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i-1][j+2];
                if (ans < temp) ans = temp;
            }
            if (i+2 < n && j+1 < m) {
                int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+2][j+1];
                if (ans < temp) ans = temp;
            }
            if (i+1 < n && j+2 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i+1][j];
                if (ans < temp) ans = temp;
            }
            if (i+2 < n && j+1 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i+1][j+1] + a[i+2][j+1];
                if (ans < temp) ans = temp;
            }
            if (i+1 < n && j+1 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i+1][j] + a[i+1][j+1];
                if (ans < temp) ans = temp;
            }
            if (i-1 >= 0 && j+2 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i-1][j+1] + a[i-1][j+2];
                if (ans < temp) ans = temp;
            }
            if (i+2 < n && j+1 < m) {
                int temp = a[i][j] + a[i+1][j] + a[i+1][j+1] + a[i+2][j+1];
                if (ans < temp) ans = temp;
            }
            if (i+1 < n && j+2 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i+1][j+1] + a[i+1][j+2];
                if (ans < temp) ans = temp;
            }
            if (i+2 < n && j-1 >= 0) {
                int temp = a[i][j] + a[i+1][j] + a[i+1][j-1] + a[i+2][j-1];
                if (ans < temp) ans = temp;
            }
            if (j+2 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i][j+2];
                if (i-1 >= 0) {
                    int temp2 = temp + a[i-1][j+1];
                    if (ans < temp2) ans = temp2;
                }
                if (i+1 < n) {
                    int temp2 = temp + a[i+1][j+1];
                    if (ans < temp2) ans = temp2;
                }
            }
            if (i+2 < n) {
                int temp = a[i][j] + a[i+1][j] + a[i+2][j];
                if (j+1 < m) {
                    int temp2 = temp + a[i+1][j+1];
                    if (ans < temp2) ans = temp2;
                }
                if (j-1 >= 0) {
                    int temp2 = temp + a[i+1][j-1];
                    if (ans < temp2) ans = temp2;
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

이와 같이, 하나의 반복문에서 if문으로 제한을 두는게 조금 더 보기에 편했다.

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

#include <iostream>
using namespace std;
int a[500][500];
int block[19][3][2] = {	// 19개의 테트로미노를 미리 정의
    {{0,1}, {0,2}, {0,3}},
    {{1,0}, {2,0}, {3,0}},
    {{1,0}, {1,1}, {1,2}},
    {{0,1}, {1,0}, {2,0}},
    {{0,1}, {0,2}, {1,2}},
    {{1,0}, {2,0}, {2,-1}},
    {{0,1}, {0,2}, {-1,2}},
    {{1,0}, {2,0}, {2,1}},
    {{0,1}, {0,2}, {1,0}},
    {{0,1}, {1,1}, {2,1}},
    {{0,1}, {1,0}, {1,1}},
    {{0,1}, {-1,1}, {-1,2}},
    {{1,0}, {1,1}, {2,1}},
    {{0,1}, {1,1}, {1,2}},
    {{1,0}, {1,-1}, {2,-1}},
    {{0,1}, {0,2}, {-1,1}},
    {{0,1}, {0,2}, {1,1}},
    {{1,0}, {2,0}, {1,1}},
    {{1,0}, {2,0}, {1,-1}},
};
int main() {
    int n, m;
    cin >> n >> m;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            for (int k=0; k<19; k++) {
                bool ok = true;
                int sum = a[i][j];
                for (int l=0; l<3; l++) {
                    int x = i+block[k][l][0];
                    int y = j+block[k][l][1];
                    if (0 <= x && x < n && 0 <= y && y < m) {
                        sum += a[x][y];
                    } else {
                        ok = false;
                        break;
                    }
                }
                if (ok && ans < sum) {
                    ans = sum;
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

이렇게 코드를 간편화할 수도 잇겠지만, 실전에서는 실력에 맞게 직접 맵핑하는 방식을 사용하는 것이 맞는 것 같다. 코드가 직관적일수록 이해도 빠르고 디버깅도 쉽기 때문이다.

ProblemSolving, BOJ
BOJ Brute Force Simulation
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.

댓글

아직 댓글이 없습니다