문제
https://www.acmicpc.net/problem/12100
풀이
보드의 크기 N은 1 ≤ N ≤ 20이며 최대 5번 이동이라는 제약으로 인해 dfs로 풀어도 시간초과가 나지 않겠다는 생각을 하였다. 정해진 방향으로 숫자가 모두 밀렸을 때를 리스트에 대한 배열로 정의하여 갱신한 후 다시 보드에 옮기는 작업을 반복하였다. 다만, 생각해야 할 부분이 조금 있었다.
Case
| 2 | 2 | 4 |
| ... | ... | ... |
| ... | ... | ... |
이러한 경우 왼쪽으로 밀었을 때 결과는 우선 다음과 같아야 한다.
| 4 | 4 | ... |
| ... | ... | ... |
| ... | ... | ... |
하지만... 이를 간과하고 처음에 아래와 같은 과정을 생각했다.
잘못된 생각
왼쪽에서 오른쪽으로 탐색하며 리스트에 값을 넣으면서 리스트의 크기가 2 이상이면 마지막 요소 두 개가 같으면 합치는 쪽으로 생각했다.
하지만, 반례가 있었다.
반례
2 2 4 ... ... ... ... ... ...
↓
4 4 ... ... ... ... ... ... ...
↓
4 ... ... ... ... ... ... ... ...
하지만, 위와 같이 구현해버리면 한 번만 왼쪽으로 밀었을 뿐인데 두 번 이동된 효과가 나타나게 된다.
이러한 문제를 해결하기 위해 한 쌍의 숫자가 합쳐지면 그 숫자는 신경쓰지 않고 다른 숫자 쌍을 찾았을 때 합치도록 변경하였다. 이따 첨부할 코드 중에서는 이를 hasFront라는 변수를 두어 제어하였다.
코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
public class Main {
static int answer = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[][] map = new int[n][n];
for (int i = 0; i < n; i++) {
String[] inputs = br.readLine().split(" ");
for (int j = 0; j < n; j++) {
map[i][j] = Integer.parseInt(inputs[j]);
}
}
func(0, map);
bw.write(Integer.toString(answer));
bw.flush();
bw.close();
br.close();
}
static void func(int depth, int[][] map) {
if (depth == 5) {
int max = 0;
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map.length; j++) {
if (max < map[i][j]) {
max = map[i][j];
}
}
}
if (answer < max) {
answer = max;
}
return;
}
for (int i = 1; i <= 4; i++) {
func(depth + 1, getRes(i, map));
}
}
static int[][] getRes(int type, int[][] map) {
List<Integer>[] lists;
int[][] newMap = new int[map.length][map.length];
if (type == 1) {
// 상
lists = getList(map, type);
for (int i = 0; i < lists.length; i++) {
for (int j = 0; j < lists[i].size(); j++) {
newMap[j][i] = lists[i].get(j);
}
}
return newMap;
}
if (type == 2) {
// 하
lists = getList(map, type);
for (int i = 0; i < lists.length; i++) {
for (int j = 0; j < lists[i].size(); j++) {
newMap[lists.length - j - 1][i] = lists[i].get(j);
}
}
return newMap;
}
if (type == 3) {
// 좌
lists = getList(map, type);
for (int i = 0; i < lists.length; i++) {
for (int j = 0; j < lists[i].size(); j++) {
newMap[i][j] = lists[i].get(j);
}
}
return newMap;
}
if (type == 4) {
// 우
lists = getList(map, type);
for (int i = 0; i < lists.length; i++) {
for (int j = 0; j < lists[i].size(); j++) {
newMap[lists.length - i - 1][j] = lists[i].get(j);
}
}
return newMap;
}
return null;
}
static List<Integer>[] getList(int[][] map, int type) {
List<Integer>[] lists = new ArrayList[map.length]; // 반환될 리스트
for (int i = 0; i < map.length; i++) {
lists[i] = new ArrayList<>();
}
boolean hasFront = false;
if (type == 1) {
// 상
for (int i = 0; i < map.length; i++) {
hasFront = false;
for (int j = 0; j < map.length; j++) {
if (map[j][i] == 0) {
continue;
}
lists[i].add(map[j][i]);
if (!hasFront) {
hasFront = true;
} else {
int size = lists[i].size();
int a = lists[i].get(size - 1);
int b = lists[i].get(size - 2);
if (a == b) {
hasFront = false;
lists[i].remove(size - 1);
lists[i].remove(size - 2);
lists[i].add(a * 2);
}
}
}
}
return lists;
}
if (type == 2) {
// 하
for (int i = 0; i < map.length; i++) {
hasFront = false;
for (int j = map.length - 1; j >= 0; j--) {
if (map[j][i] == 0) {
continue;
}
lists[i].add(map[j][i]);
if (!hasFront) {
hasFront = true;
} else {
int size = lists[i].size();
int a = lists[i].get(size - 1);
int b = lists[i].get(size - 2);
if (a == b) {
hasFront = false;
lists[i].remove(size - 1);
lists[i].remove(size - 2);
lists[i].add(a * 2);
}
}
}
}
return lists;
}
if (type == 3) {
// 좌
for (int i = 0; i < map.length; i++) {
hasFront = false;
for (int j = 0; j < map.length; j++) {
if (map[i][j] == 0) {
continue;
}
lists[i].add(map[i][j]);
if (!hasFront) {
hasFront = true;
} else {
int size = lists[i].size();
int a = lists[i].get(size - 1);
int b = lists[i].get(size - 2);
if (a == b) {
hasFront = false;
lists[i].remove(size - 1);
lists[i].remove(size - 2);
lists[i].add(a * 2);
}
}
}
}
return lists;
}
if (type == 4) {
// 우
for (int i = 0; i < map.length; i++) {
hasFront = false;
for (int j = map.length - 1; j >= 0; j--) {
if (map[i][j] == 0) {
continue;
}
lists[i].add(map[i][j]);
if (!hasFront) {
hasFront = true;
} else {
int size = lists[i].size();
int a = lists[i].get(size - 1);
int b = lists[i].get(size - 2);
if (a == b) {
hasFront = false;
lists[i].remove(size - 1);
lists[i].remove(size - 2);
lists[i].add(a * 2);
}
}
}
}
return lists;
}
return null;
}
}
Coding Duck