문제 링크
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
완전탐색 문제이다. 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
|
#include <cstdio>
int map[501][501],ans=0;
int check[501][501];
int n,m;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
void dfs(int x,int y,int depth,int sum){
if(depth==4){ans=ans<sum?sum:ans;return;}
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(x>=0&&x<n&&y>=0&&y<m){
if(!check[nx][ny]){
check[nx][ny]=1;
dfs(nx,ny,depth+1,sum+map[nx][ny]);
check[nx][ny]=0;
}
}
}
}
void ou(int x,int y){
//ㅓ
if(x-1>=0&&x+1<n&&y+1<m&&y>=0){
int tmp=map[x][y]+map[x][y+1]+map[x-1][y+1]+map[x+1][y+1];
ans=ans<tmp?tmp:ans;
//ans=ans<tmp?printf(" %d, %d ",x,y):ans;
}
//ㅏ
if(x-1>=0&&x+1<n&&y<m&&y-1>=0){
int tmp=map[x][y]+map[x][y-1]+map[x-1][y-1]+map[x+1][y-1];
ans=ans<tmp?tmp:ans;
//ans=ans<tmp?printf(" %d, %d ",x,y):ans;
}
//ㅗ
if(x>=0&&x+1<n&&y+1<m&&y-1>=0){
int tmp=map[x][y]+map[x+1][y+1]+map[x+1][y]+map[x+1][y-1];
ans=ans<tmp?tmp:ans;
//ans=ans<tmp?printf(" %d, %d ",x,y):ans;
}
//ㅜ
if(x-1>=0&&x<n&&y+1<m&&y-1>=0){
int tmp=map[x][y]+map[x-1][y-1]+map[x-1][y]+map[x-1][y+1];
ans=ans<tmp?tmp:ans;
//ans=ans<tmp?printf(" %d, %d ",x,y):ans;
}
}
void solve(){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
check[i][j]=1;
dfs(i,j,1,map[i][j]);
ou(i,j);
check[i][j]=0;
}
}
}
main(){
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&map[i][j]);
solve();
printf("%d",ans);
}
|
cs |
입력을 받고 dfs를 구현까지는 했지만 dfs의 방문체크를 해주지 않아서 오류가 발생해 check함수를 만들어 방문지 check를 구현하였고 또한 ㅗ모양은 dfs로 구현이 불가능해 일일히 하드코딩했다. 그럼 다음 문제로 쓩~
PS. 티스토리 글쓰기 이전께 나은거 같은데ㅜ
'Algorithm > 문제 풀이 (Problem Solving)' 카테고리의 다른 글
| [C++,구현] 백준 17144번 미세먼지 안녕! 문제풀이 (0) | 2019.04.25 |
|---|---|
| [C++,구현] 백준 14890번 경사로 문제풀이 (0) | 2019.04.06 |
| [C++,구현] 백준 14891번 톱니바퀴 문제풀이 (0) | 2019.03.27 |
| [C++,구현] 백준 14499번 주사위 굴리기 문제풀이 (0) | 2019.03.14 |
| [C++,DP] 백준 2294번 동전2 문제풀이 (0) | 2019.03.08 |
댓글