반응형
📖 문제
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
💡 풀이 방식
• 구현, 브루트포스
테트로미노로 만들 수 있는 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
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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
|
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static int[][] map;
static int max = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
for(int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j = 0 ; j < M ; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
shape1();
shape2();
shape3();
shape4();
shape5();
shape6();
shape7();
shape8();
shape9();
shape1011();
shape1213();
shape1415();
shape1617();
shape1819();
System.out.println(max);
}
// 가로(ㅡ)
private static void shape1() {
for(int i = 0 ; i < N ; i++) {
for(int j = 0 ; j <= M - 4 ; j++) {
int tmp = map[i][j] + map[i][j + 1] + map[i][j + 2] + map[i][j + 3];
max = Math.max(max, tmp);
}
}
}
// 세로(|)
private static void shape2() {
for(int i = 0 ; i <= N - 4 ; i++) {
for(int j = 0 ; j < M ; j++) {
int tmp = map[i][j] + map[i + 1][j] + map[i + 2][j] + map[i + 3][j];
max = Math.max(max, tmp);
}
}
}
// 정사각형
private static void shape3() {
for(int i = 0 ; i <= N - 2 ; i++) {
int tmp = 0;
for(int j = 0 ; j <= M - 2 ; j++) {
tmp = map[i][j] + map[i][j + 1] + map[i + 1][j] + map[i + 1][j + 1];
max = Math.max(max, tmp);
}
}
}
// ㄴ #1
private static void shape4() {
for(int i = 0 ; i <= N - 3 ; i++) {
for(int j = 0 ; j <= M - 2 ; j++) {
int tmp = map[i][j] + map[i + 1][j] + map[i + 2][j] + map[i + 2][j + 1];
max = Math.max(max, tmp);
}
}
}
// ㄴ #2 : ㄴ #1 반시계 방향 90도 회전
private static void shape5() {
for(int i = 0 ; i <= N - 2 ; i++) {
for(int j = 0 ; j <= M - 3 ; j++) {
int tmp = map[i][j + 2] + map[i + 1][j] + map[i + 1][j + 1] + map[i + 1][j + 2];
max = Math.max(max, tmp);
}
}
}
// ㄴ #3 : ㄴ #1 반시계 방향 180도 회전
private static void shape6() {
for(int i = 0 ; i <= N - 3 ; i++) {
for(int j = 0 ; j <= M - 2 ; j++) {
int tmp = map[i][j] + map[i][j + 1] + map[i + 1][j + 1] + map[i + 2][j + 1];
max = Math.max(max, tmp);
}
}
}
// ㄴ #4 : ㄴ #1 반시계 방향 270도 회전
private static void shape7() {
for(int i = 0 ; i <= N - 2 ; i++) {
for(int j = 0 ; j <= M - 3 ; j++) {
int tmp = map[i][j] + map[i][j + 1] + map[i][j + 2] + map[i + 1][j];
max = Math.max(max, tmp);
}
}
}
// ㄴ #5 : ㄴ #1 좌우대칭
private static void shape8() {
for(int i = 0 ; i <= N - 3 ; i++) {
for(int j = 0 ; j <= M - 2 ; j++) {
int tmp = map[i + 2][j] + map[i][j + 1] + map[i + 1][j + 1] + map[i + 2][j + 1];
max = Math.max(max, tmp);
}
}
}
// ㄴ #5 : ㄴ #3 좌우대칭
private static void shape9() {
for(int i = 0 ; i <= N - 3 ; i++) {
for(int j = 0 ; j <= M - 2 ; j++) {
int tmp = map[i][j] + map[i][j + 1] + map[i + 1][j] + map[i + 2][j];
max = Math.max(max, tmp);
}
}
}
// ㄴ #4 좌우대칭, ㄴ #2 좌우대칭
private static void shape1011() {
for(int i = 0 ; i <= N - 2 ; i++) {
for(int j = 0 ; j <= M - 3 ; j++) {
int tmp1 = map[i][j] + map[i][j + 1] + map[i][j + 2] + map[i + 1][j + 2];
int tmp2 = map[i][j] + map[i + 1][j] + map[i + 1][j + 1] + map[i + 1][j + 2];
max = Math.max(max, Math.max(tmp1, tmp2));
}
}
}
// ㄹ #1, ㄹ #1 좌우대칭
private static void shape1213() {
for(int i = 0 ; i <= N - 3 ; i++) {
for(int j = 0 ; j <= M - 2 ; j++) {
int tmp1 = map[i][j] + map[i + 1][j] + map[i + 1][j + 1] + map[i + 2][j + 1];
int tmp2 = map[i][j + 1] + map[i + 1][j] + map[i + 1][j + 1] + map[i + 2][j];
max = Math.max(max, Math.max(tmp1, tmp2));
}
}
}
// ㄹ #2 (ㄹ #1 반시계 방향 90도 회전), ㄹ #2 좌우대칭
private static void shape1415() {
for(int i = 0 ; i <= N - 2 ; i++) {
for(int j = 0 ; j <= M - 3 ; j++) {
int tmp1 = map[i][j + 1] + map[i][j + 2] + map[i + 1][j] + map[i + 1][j + 1];
int tmp2 = map[i][j] + map[i][j + 1] + map[i + 1][j + 1] + map[i + 1][j + 2];
max = Math.max(max, Math.max(tmp1, tmp2));
}
}
}
// ㅜ, ㅗ
private static void shape1617() {
for(int i = 0 ; i <= N - 2 ; i++) {
for(int j = 0 ; j <= M - 3 ; j++) {
int tmp1 = map[i][j] + map[i][j + 1] + map[i][j + 2] + map[i + 1][j + 1];
int tmp2 = map[i][j + 1] + map[i + 1][j] + map[i + 1][j + 1] + map[i + 1][j + 2];
max = Math.max(max, Math.max(tmp1, tmp2));
}
}
}
//
private static void shape1819() {
for(int i = 0 ; i <= N - 3 ; i++) {
for(int j = 0 ; j <= M - 2 ; j++) {
int tmp1 = map[i][j + 1] + map[i + 1][j] + map[i + 1][j + 1] + map[i + 2][j + 1];
int tmp2 = map[i][j] + map[i + 1][j] + map[i + 1][j + 1] + map[i + 2][j];
max = Math.max(max, Math.max(tmp1, tmp2));
}
}
}
}
|
cs |
➕ 다른 풀이 방식
- DFS를 활용한 풀이!!!! 깊이가 4인 dfs로 탐색하고 ㅜ 모양에 따로 구하는 조합 메소드 추가.. 이렇게 생각할 수도 있군!!!
[백준] 14500번: 테트로미노 - JAVA
🔗 문제 링크 BOJ 14500번: 테트로미노 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안
girawhale.tistory.com
[백준] 14500 - 테트로미노 자바
문제 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형
developer-u.tistory.com
[백준] 14500. 테트로미노 (Java)
문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된
hanyeop.tistory.com
💦 어려웠던 점
- 구현은 1시간 내에 했는데, 메소드 하나 빠뜨려서 틀려서 이거 찾느라 추가로 1시간 더 삽질했다,,,,,^^^^^^
- 다음엔 DFS로 풀어보겠다,,,
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V | 0210 |
(+2회독 240210)
연속된 4개의 점 뽑는 건 dfs로 진행하고, ㅜ자 모양 처리는 직접 좌표값을 구해 진행했다.
코드 확인하기
|
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
|
import java.util.*;
import java.io.*;
public class Main {
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static int N, M;
static int[][] grid;
static boolean[][] visited; // (i, j) 위치 값 중복해 뽑지 않기 위한 배열
static int max = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
grid = new int[N][M];
visited = new boolean[N][M];
for(int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j = 0 ; j < M ; j++) {
grid[i][j] = Integer.parseInt(st.nextToken());
}
}
// 위치 (i, j)부터 원소 4개 선택하기 (백트래킹)
for(int i = 0 ; i < N ; i++) {
for(int j = 0 ; j < M ; j++) {
visited[i][j] = true;
dfs(i, j, 1, grid[i][j]);
visited[i][j] = false;
check(i, j);
}
}
System.out.println(max);
}
private static void dfs(int x, int y, int depth, int sum) {
if(depth == 4) {
max = Math.max(max, sum);
return;
}
for(int d = 0 ; d < 4 ; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if(inRange(nx,ny) && !visited[nx][ny]) {
visited[nx][ny] = true;
dfs(nx, ny, depth +1, sum + grid[nx][ny]);
visited[nx][ny] = false;
}
}
}
private static void check(int x, int y) {
if(x + 1 < N && y + 2 < M) // ㅜ
max = Math.max(max, grid[x][y] + grid[x][y+1] + grid[x][y+2] + grid[x+1][y+1]);
if(x + 2 < N && y + 1 < M) // ㅓ
max = Math.max(max, grid[x][y + 1] + grid[x+1][y] + grid[x+1][y+1] + grid[x+2][y+1]);
if(x + 2 < N && y + 1 < M) // ㅏ
max = Math.max(max, grid[x][y] + grid[x+1][y] + grid[x+2][y] + grid[x+1][y+1]);
if(x + 1 < N && y + 2 < M) // ㅗ
max = Math.max(max, grid[x][y+1] + grid[x+1][y] + grid[x+1][y+1] + grid[x+1][y+2]);
}
private static boolean inRange(int x, int y) {
return (0 <= x && x < N && 0 <= y && y < M);
}
}
|
cs |
(참고)
✔ TC 참고
글 읽기 - << 테케 공유 >>
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
반응형
'코테 > 백준' 카테고리의 다른 글
| [백준/JAVA] 21608번: 상어 초등학교 (0) | 2023.12.28 |
|---|---|
| [백준/JAVA] 12933번: 오리 (0) | 2023.12.28 |
| [백준/JAVA] 20436번: ZOAC 3 (0) | 2023.12.26 |
| [백준/JAVA] 2578번: 빙고 (0) | 2023.12.26 |
| [백준/JAVA] 17406번: 배열 돌리기 4 (0) | 2023.12.19 |
