BOJ#4920 테트리스 게임
* 문제
이전에 풀어봤던 14500번 테트로미노(삼성 기출)와 비슷한 문제입니다.
* 풀이
14500번의 경우 (ㅓ, ㅏ, ㅗ, ㅜ)를 제외하고 다른 모양은 전부 dfs로 탐색이 가능했지만,
4920번의 경우 위 경우 이외에도 dfs로 탐색이 불가능한 경우가 있습니다. (예 : ㄱ 등등)
따라서 dfs 탐색을 사용하지 않고 패턴을 미리 정해놓은 후 매칭시키는 방법으로 시뮬레이션 하였습니다.
* 나의 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static final int[] dRow = { 0, -1, 0, 1 };
static final int[] dCol = { -1, 0, 1, 0 };
static final int[][] patternRow = {
{ 1, 1, 1 }, { 0, 0, 0 },
{ 0, 1, 0 }, { 1, 0, 1 },
{ 0, 0, 1 }, { 1, 1, 0 }, { 0, 0, -1 }, { -1, -1, 0 },
{ 0, 1, 0}
};
static final int[][] patternCol = {
{ 0, 0, 0 }, { 1, 1, 1 },
{ 1, 0, 1 }, { 0, -1, 0 },
{ 1, 1, 0 }, { 0, 0, -1 }, {-1, -1, 0 }, { 0, 0, 1 },
{ 1, 0, -1}
};
static int N;
static int[][] map = new int[101][101];
static int maxSum = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int idx = 0;
while (true) {
idx++;
maxSum = Integer.MIN_VALUE;
// Input
N = Integer.parseInt(br.readLine().trim());
if (N == 0) break;
for (int i = 0; i < N; i++) {
String inputLine = br.readLine().trim();
String[] line = inputLine.split("\\p{Blank}+");
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(line[j]);
}
}
// Solve
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
// Pattern1
solve1(row, col);
// Pattern2 (+)
solve2(row, col);
}
}
System.out.println(idx + ". " + maxSum);
} // ~ test case loop
} // ~ main
static void solve1(int row, int col) {
for (int i = 0; i < 9; i++) {
int sum = map[row][col];
boolean isMatchPattern = true;
int nextRow = row;
int nextCol = col;
for (int j = 0; j < 3; j++) {
nextRow += patternRow[i][j];
nextCol += patternCol[i][j];
if (nextRow < 0 || nextCol < 0 || nextRow >= N || nextCol >= N) {
isMatchPattern = false;
break;
}
sum += map[nextRow][nextCol];
}
if (isMatchPattern) {
maxSum = maxSum < sum ? sum : maxSum;
}
}
}
static void solve2(int row, int col) {
int nInvalidity = 0;
int minValue = Integer.MAX_VALUE;
int crossSum = map[row][col];
for (int i = 0; i < 4; i++) {
int nextRow = row + dRow[i];
int nextCol = col + dCol[i];
if (nextRow < 0 || nextCol < 0 || nextRow >= N || nextCol >= N) {
nInvalidity++;
continue;
}
crossSum += map[nextRow][nextCol];
minValue = minValue > map[nextRow][nextCol] ? map[nextRow][nextCol] : minValue;
}
switch (nInvalidity) {
case 0:
crossSum -= minValue;
case 1:
maxSum = maxSum < crossSum ? crossSum : maxSum;
break;
case 2:
case 3:
break;
}
}
}
'Algorithm > 시뮬레이션' 카테고리의 다른 글
BOJ#3019 테트리스 (0) | 2017.10.18 |
---|---|
BOJ#11559 Puyo Puyo (0) | 2017.09.21 |
BOJ#14503 로봇 청소기 (0) | 2017.04.22 |
BOJ#3190 뱀 (5) | 2017.04.15 |
BOJ#2931 가스관 (1) | 2017.04.14 |