👀 문제
https://www.acmicpc.net/problem/14500
👊 도전
1. 설계
- ㅗ를 제외한 4가지 방법은 DFS로 해결한다.
- ㅗ는 ㅗ, ㅜ, ㅓ, ㅏ 4가지로 따로 계산한다.
2. 구현 (성공 코드)
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
import java.util.Scanner;
/**
* @author HEESOO
*
*/
public class Main {
static int n, m;
static int[][] map;
static boolean[][] visit;
static int max;
static int[] dx= {0,0,-1,1};
static int[] dy= {1,-1,0,0};
public static void dfs(int x, int y, int depth, int sum) {
if(depth==4) {
max=Math.max(max, sum);
return;
}
for(int i=0;i<4;i++) {
int xx=x+dx[i];
int yy=y+dy[i];
if(0<=xx&&xx<n && 0<=yy&&yy<m) {
if(!visit[xx][yy]) {
visit[xx][yy]=true;
dfs(xx, yy, depth+1, sum+map[xx][yy]);
visit[xx][yy]=false;
}
}
}
}
public static void special(int x, int y) {
int[][][] dot= {{{0,0},{0,1},{-1,0},{1,0}},
{{0,0},{-1,0},{0,-1},{1,0}},
{{0,0},{0,1},{-1,0},{0,-1}},
{{0,0},{0,1},{1,0},{0,-1}}};
for(int i=0;i<4;i++) {
int sum=0;
boolean flag=true;
for(int j=0;j<4;j++) {
int xx=x+dot[i][j][0];
int yy=y+dot[i][j][1];
if(0<=xx&&xx<n && 0<=yy&&yy<m) {
sum+=map[xx][yy];
}
else {
flag=false;
break;
}
}
if(flag) max=Math.max(max, sum);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
n=scan.nextInt();
m=scan.nextInt();
map=new int[n][m];
visit=new boolean[n][m];
max=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
map[i][j]=scan.nextInt();
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
visit[i][j]=true;
dfs(i, j, 0, 0);
visit[i][j]=false;
special(i,j);
}
}
System.out.println(max);
}
}
3. 결과
🤟 성공 🤟
4. 설명
- DFS를 이용하여 ㅗ를 제외한 4가지를 해결한다
- ㅗ를 제외한 4가지 방법은 DFS로 테트로미노의 정사각형들을 방문할 수 있다.
- ㅗ는 불가능하다. ㅗ를 모두 방문하려면 재방문을 해야하는데, DFS에서는 재방문을 하지 않기 때문이다.
- 파라미터 i, j를 기준으로 상하좌우에 있는 노드에 방문 가능한지 체크한 후, 가능하다면 그 노드로 이동한다.
- 테트로미노는 4개의 노드들로 이루어져있으므로, depth==4가 될 때의 sum을 max와 비교해 저장하면 된다.
- DFS로 방문한 테트로미노는 ㅗ를 제외한 4가지 모양 중 하나를 무조건 만족한다.
- ㅗ를 체크한다
- ㅗ는 회전과 뒤집었을 때 ㅗ, ㅜ, ㅓ ,ㅏ가 가능하다.
- 위의 4가지 경우를 3차원배열로 인덱스를 저장한다. dot[i][j][k]일때 i는 4가지 종류 중 하나를 뜻하고, j는 i종류의 x값, k는 y값을 뜻한다.
- 인덱스 범위를 벗어나지 않는다면 노드값을 sum에 저장한다.
- 중간에 인덱스 범위를 초과한다면 4개의 노드를 방문할 수 없어 4가지 모양 중 하나를 만들 수 없다는 뜻이므로 flag=false로 바꾼 후 break한다.
- flag=false인 경우 해당 테트로미노는 만들 수 없다는 뜻이므로 지금까지 누적합한 sum은 버린다.
👏 해결 완료!
참고
- [백준 14500] 테트로미노 https://hyeooona825.tistory.com/60
- 백준 14500번. 테트로미노 (Java, Python) https://bcp0109.tistory.com/20