Algorithm/시뮬레이션

BOJ#4920 테트리스 게임

밤이2209 2017. 10. 17. 16:33

BOJ#4920 테트리스 게임


* 문제


이전에 풀어봤던 14500번 테트로미노(삼성 기출)와 비슷한 문제입니다.

* 풀이

14500번의 경우 (ㅓ, ㅏ, ㅗ, ㅜ)를 제외하고 다른 모양은 전부 dfs로 탐색이 가능했지만,
4920번의 경우 위 경우 이외에도 dfs로 탐색이 불가능한 경우가 있습니다. (예 : ㄱ 등등)

따라서 dfs 탐색을 사용하지 않고 패턴을 미리 정해놓은 후 매칭시키는 방법으로 시뮬레이션 하였습니다.





* 나의 코드

https://github.com/stack07142/BOJ/blob/f0d9bf85e203ff075cbf53506fb38d625f5115a3/BOJ%234920/src/Main.java


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