테트로미노
백준 [14500] 테트로미노
풀이
테트로미노 탐색은 dfs로 진행하였고, 凸 모양의 테트로미노는 따로 조건처리
- dfs(int r, int c, int n, int sum, int chk, boolean[][] visited)
- r, c : 현재 좌표
- sum : 현재까지의 총 합
- chk : 凸 모양을 위해 어디서 온 방향인지 체크. 볼록한 부분이 어디로 볼록해져야 할지 정하기 위해.
- visited : 방문체크
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int[][] map;
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
static int ans;
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());
}
}
ans = 0;
boolean[][] visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
visited[i][j] = true;
dfs(i, j, 1, map[i][j], 0, visited);
visited[i][j] = false;
}
}
System.out.println(ans);
}
public static void dfs(int r, int c, int n, int sum, int chk, boolean[][] visited) {
if (n == 4) {
ans = Math.max(ans, sum);
return;
}
if (n == 2) {
int num1 = 0;
int num2 = 0;
int idx = -1;
switch (chk) {
case 0:
case 1:
num1 = isRange(r + dx[2], c + dy[2]) ? map[r + dx[2]][c + dy[2]] : -1;
num2 = isRange(r + dx[3], c + dy[3]) ? map[r + dx[3]][c + dy[3]] : -1;
if (num1 >= num2)
idx = 2;
else
idx = 3;
break;
case 2:
case 3:
num1 = isRange(r + dx[0], c + dy[0]) ? map[r + dx[0]][c + dy[0]] : -1;
num2 = isRange(r + dx[1], c + dy[1]) ? map[r + dx[1]][c + dy[1]] : -1;
if (num1 >= num2)
idx = 0;
else
idx = 1;
break;
}
int num = Math.max(num1, num2);
if (isRange(r + dx[idx], c + dy[idx]) && num > 0) {
visited[r + dx[idx]][c + dy[idx]] = true;
dfs(r, c, n + 1, sum + num, chk, visited);
visited[r + dx[idx]][c + dy[idx]] = false;
}
}
for (int i = 0; i < 4; i++) {
int x = r + dx[i];
int y = c + dy[i];
if (isRange(x, y) && !visited[x][y]) {
visited[x][y] = true;
dfs(x, y, n + 1, sum + map[x][y], i, visited);
visited[x][y] = false;
}
}
}
public static boolean isRange(int x, int y) {
return x >= 0 && y >= 0 && x < N && y < M;
}
}