알고리즘 문제/BOJ

14500번 테트로미노

parkit 2018. 8. 30. 14:00
728x90
반응형

두 번째 풀이 방법은 신선하여 첨부하였다.




삼성 SW 역량 테스트 기출 문제이다.


방문 여부(visit)를 잘 생각해줘야한다. 


방문 여부를 생각하지 못 하여(다음 테트로미노를 위한 재사용), 다른 분의 코드를 참고하였다.





이 문제를 통해 기억해야할 것

1. 36, 40, 92, 98 번 째 줄은 반드시 써줘야한다. 

그래야 다음 모양의 테트로미노를 계산할 때, 다시 한 번 정사각형 한 칸의 크기를 사용할 수 있다.

2. otherShape 함수는 DFS로는 탐색할 수 없는 모양(ㅗ)을 위해 따로 만들어준 함수다.





https://www.acmicpc.net/problem/14500






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
#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int map[501][501] = { 0, };
 
bool visit[501][501] = { false, };
 
int N = 0, M = 0;
 
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
 
int result = 0;
 
int DFS(int r, int c, int Cnt)
{
    if (Cnt == 4) return map[r][c];
 
    int MAX = 0;
 
    for (int i = 0; i < 4; i++)
    {
        int y = r + dy[i];
        int x = c + dx[i];
 
        if (0 <= y && y < N && 0 <= x && x < M && !visit[y][x])
        {
            visit[y][x] = true;
 
            MAX = max(MAX, map[r][c] + DFS(y, x, Cnt + 1));
 
            visit[y][x] = false;
        }
    }
 
    return MAX;
}
 
int otherShape(int y, int x)
{
    int ret = 0;
 
    if (y - 1 >= 0 && x - 1 >= 0 && x + 1 < M) // ㅗ
    {
        ret = max(ret, map[y - 1][x] + map[y][x - 1] + map[y][x] + map[y][x + 1]);
    }
 
    if (y - 1 >= 0 && y + 1 < N && x + 1 < M) // ㅏ
    {
        ret = max(ret, map[y - 1][x] + map[y][x] + map[y + 1][x] + map[y][x + 1]);
    }
 
    if (y + 1 < N && x - 1 >= 0 && x + 1 < M) // ㅜ
    {
        ret = max(ret, map[y + 1][x] + map[y][x - 1] + map[y][x + 1] + map[y][x]);
    }
 
    if (y - 1 >= 0 && y + 1 < N && x - 1 >= 0) // ㅓ
    {
        ret = max(ret, map[y - 1][x] + map[y][x] + map[y + 1][x] + map[y][x - 1]);
    }
 
    return ret;
}
 
int main(void)
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (!visit[i][j])
            {
                visit[i][j] = true;
 
                result = max(result, DFS(i, j, 1));
 
                result = max(result, otherShape(i, j));
 
                visit[i][j] = false;
            }
        }
    }
 
    printf("%d\n", result);
 
    return 0;
}
cs







아래는 신박한 풀이 방법이다.



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
#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 505
#define Min -5000
 
int R, C, m[Max][Max];
 
vector<vector<vector<int> > > v = {
    { // 0
        { 1, 1, 1, 1 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 1
        { 1, 0, 0, 0 },
        { 1, 0, 0, 0 },
        { 1, 0, 0, 0 },
        { 1, 0, 0, 0 }
    },
    { // 2
        { 1, 1, 0, 0 },
        { 1, 1, 0, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 3
        { 1, 0, 0, 0 },
        { 1, 0, 0, 0 },
        { 1, 1, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 4
        { 1, 1, 1, 0 },
        { 1, 0, 0, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 5
        { 1, 1, 0, 0 },
        { 0, 1, 0, 0 },
        { 0, 1, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 6
        { 0, 0, 1, 0 },
        { 1, 1, 1, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 7
        { 0, 1, 0, 0 },
        { 0, 1, 0, 0 },
        { 1, 1, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 8
        { 1, 0, 0, 0 },
        { 1, 1, 1, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 9
        { 1, 1, 0, 0 },
        { 1, 0, 0, 0 },
        { 1, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 10
        { 1, 1, 1, 0 },
        { 0, 0, 1, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 11
        { 1, 0, 0, 0 },
        { 1, 1, 0, 0 },
        { 0, 1, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 12
        { 0, 1, 1, 0 },
        { 1, 1, 0, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 13
        { 0, 1, 0, 0 },
        { 1, 1, 0, 0 },
        { 1, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 14
        { 1, 1, 0, 0 },
        { 0, 1, 1, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 15
        { 1, 1, 1, 0 },
        { 0, 1, 0, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 16
        { 0, 1, 0, 0 },
        { 1, 1, 0, 0 },
        { 0, 1, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 17
        { 0, 1, 0, 0 },
        { 1, 1, 1, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    },
    { // 18
        { 1, 0, 0, 0 },
        { 1, 1, 0, 0 },
        { 1, 0, 0, 0 },
        { 0, 0, 0, 0 }
    }
};
 
int find_value(int y, int x, int k)
{
    int ret = 0;
 
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            ret += m[y + i][x + j] * v[k][i][j];
 
    return ret;
}
 
int main(void)
{
    int answer = 0;
 
    scanf("%d %d", &R, &C);
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++)    scanf("%d", &m[i][j]);
    for (int i = R; i < R + 4; i++) for (int j = 0; j < C + 4; j++) m[i][j] = Min;
    for (int i = 0; i < R + 4; i++) for (int j = C; j < C + 4; j++)    m[i][j] = Min;
    
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            for (int k = 0; k < v.size(); k++)        
                answer = max(answer, find_value(i, j, k));
 
    printf("%d\n", answer);
 
    return 0;
}
cs






















728x90
반응형
저작자표시 (새창열림)