https://www.acmicpc.net/problem/12094
12094번: 2048 (Hard)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
풀이
문제를 보았을 때 알 수 있는 힌트
이전에 풀었단 2048(Easy) 문제에 5개의 경우를 10번 이동 했을때로 좀 더 반복하는 수가 늘어난 문제이다.
당연히 그대로 푼다면 간단하게 구현하였기에 시간초과가 날 것이다. 잘 짰다면 이부분도 잘 통과했겠지만 ㅠㅠ
그래서 시간을 줄이기위해 깊은 복사하는 부분을 최대한 줄였다. 이전에는 왼쪽, 오른쪽, 위, 아래 방향을 이동할때마다 깊은 복사를 하였는데 이번에는 백트래킹 되고 돌아왔을때 이전의 가지고 있던 깊은 복사를 입혀주는 형식으로 바꾸었다.
먼저 복사하냐 나중에 복사하냐로 조금 깊은 복사가 줄지 않았을까 생각한다.
다음으로는 깊은 복사 자체를 반복문 2개를 써서 했었는데 이를 반복문 1개의 clone을 이용하였을때 시간이 더 줄어들었다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int n;
static int[][] graph;
static int result;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
graph = new int[n][n];
StringTokenizer stz;
for (int i = 0; i < n; i++) {
stz = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
graph[i][j] = Integer.parseInt(stz.nextToken());
}
}
// 입력 완료
dfs(0);
System.out.println(result);
}
static void dfs(int cnt) {
if(cnt==10) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
result = Math.max(result, graph[i][j]);
}
}
return;
}
int[][] temp = new int[n][n];
temp= deepCopy(temp,graph);
left(graph);
dfs(cnt+1);
graph= deepCopy(graph,temp);
right(graph);
dfs(cnt+1);
graph= deepCopy(graph,temp);
top(graph);
dfs(cnt+1);
graph= deepCopy(graph,temp);
down(graph);
dfs(cnt+1);
graph= deepCopy(graph,temp);
// print(left(temp));
// print(right(temp));
}
static int[][] left(int[][] temp) {
for (int i = 0; i < n; i++) {
int curPoint=0;
int j=0;
int tempCount = temp[i][j];
while(true) {
j++;
if(j>n-1) break;
if(temp[i][j] ==0) continue;
if(tempCount==0) {
tempCount=temp[i][j];
continue;
}
if(temp[i][j]==tempCount) {
temp[i][curPoint++]= tempCount*2;
temp[i][j] = 0;
tempCount = 0;
}
else if(temp[i][j]!=tempCount){
temp[i][curPoint++]= tempCount;
tempCount = temp[i][j];
}
}
if(tempCount!=0) {
temp[i][curPoint++]= tempCount;
}
while(curPoint<n) {
temp[i][curPoint++] = 0;
}
}
// print(temp);
return temp;
}
static int[][] right(int[][] temp) {
for (int i = 0; i < n; i++) {
int curPoint=n-1;
int j=n-1;
int tempCount = temp[i][j];
while(true) {
j--;
if(j<0) break;
if(temp[i][j] ==0) continue;
if(tempCount==0) {
tempCount=temp[i][j];
continue;
}
if(temp[i][j]==tempCount) {
temp[i][curPoint--]= tempCount*2;
temp[i][j] = 0;
tempCount = 0;
}
else if(temp[i][j]!=tempCount){
temp[i][curPoint--]= tempCount;
tempCount = temp[i][j];
}
}
if(tempCount!=0) {
temp[i][curPoint--]= tempCount;
}
while(curPoint>-1) {
temp[i][curPoint--] = 0;
}
}
return temp;
}
static int[][] down(int[][] temp) {
for (int j = 0; j < n; j++) {
int curPoint=n-1;
int i=n-1;
int tempCount = temp[i][j];
while(true) {
i--;
if(i<0) break;
if(temp[i][j] ==0) continue;
if(tempCount==0) {
tempCount=temp[i][j];
continue;
}
if(temp[i][j]==tempCount) {
temp[curPoint--][j]= tempCount*2;
temp[i][j] = 0;
tempCount = 0;
}
else if(temp[i][j]!=tempCount){
temp[curPoint--][j]= tempCount;
tempCount = temp[i][j];
}
}
if(tempCount!=0) {
temp[curPoint--][j]= tempCount;
}
while(curPoint>-1) {
temp[curPoint--][j] = 0;
}
}
return temp;
}
static int[][] top(int[][] temp) {
for (int j = 0; j < n; j++) {
int curPoint=0;
int i=0;
int tempCount = temp[i][j];
while(true) {
i++;
if(i>n-1) break;
if(temp[i][j] ==0) continue;
if(tempCount==0) {
tempCount=temp[i][j];
continue;
}
if(temp[i][j]==tempCount) {
temp[curPoint++][j]= tempCount*2;
temp[i][j] = 0;
tempCount = 0;
}
else if(temp[i][j]!=tempCount){
temp[curPoint++][j]= tempCount;
tempCount = temp[i][j];
}
}
if(tempCount!=0) {
temp[curPoint++][j]= tempCount;
}
while(curPoint<n) {
temp[curPoint++][j] = 0;
}
}
return temp;
}
static int[][] deepCopy(int[][] temp, int[][] graph){
for (int i = 0; i < temp.length; i++) {
temp[i] = graph[i].clone();
}
return temp;
}
static void print(int[][] graph) {
for (int[] is : graph) {
System.out.println(Arrays.toString(is));
}
System.out.println();
}
}이 두가지를 다 적용하였을때 4368ms로 5000ms를 초과하지 않고 아슬아슬 통과하였다.
아마 코드의 구현 부분을 깔끔하게 구현했다면 성능이 좋지 않았을까 생각한다.
이어서 구현 부분에 필요없는 부분과 합칠수 있는 부분을 합친결과 2820ms 까지 줄일 수 있었다.
다만 1000ms대 까지 줄이려면 비트마스크를 이용하면 될듯한데 거기까지는 손대지 못하겠다..
package baekjoon12094;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int n;
static int[][] graph;
static int result;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
graph = new int[n][n];
StringTokenizer stz;
for (int i = 0; i < n; i++) {
stz = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
graph[i][j] = Integer.parseInt(stz.nextToken());
}
}
// 입력 완료
dfs(0);
System.out.println(result);
}
static void dfs(int cnt) {
if(cnt==10) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
result = Math.max(result, graph[i][j]);
}
}
return;
}
int[][] temp = new int[n][n];
temp= deepCopy(temp,graph);
left();
dfs(cnt+1);
graph= deepCopy(graph,temp);
right();
dfs(cnt+1);
graph= deepCopy(graph,temp);
top();
dfs(cnt+1);
graph= deepCopy(graph,temp);
down();
dfs(cnt+1);
graph= deepCopy(graph,temp);
}
static void left() {
for (int i = 0; i < n; i++) {
int curPoint=0;
int tempCount = 0;
for (int j = 0; j < n; j++) {
if(graph[i][j] ==0) continue;
if(graph[i][j]==tempCount) {
graph[i][curPoint-1]= tempCount*2;
tempCount = 0;
graph[i][j] = 0;
}
else{
tempCount = graph[i][j];
graph[i][j] = 0;
graph[i][curPoint++]= tempCount;
}
}
}
}
static void right() {
for (int i = 0; i < n; i++) {
int curPoint=n-1;
int tempCount = 0;
for (int j = n-1; j > -1; j--) {
if(graph[i][j] ==0) continue;
if(graph[i][j]==tempCount) {
graph[i][curPoint+1]= tempCount*2;
graph[i][j] = 0;
tempCount = 0;
}
else {
tempCount = graph[i][j];
graph[i][j] = 0;
graph[i][curPoint--]= tempCount;
}
}
}
}
static void down() {
for (int j = 0; j < n; j++) {
int curPoint=n-1;
int tempCount =0;
for (int i = n-1; i > -1; i--) {
if(graph[i][j] ==0) continue;
if(graph[i][j]==tempCount) {
graph[curPoint+1][j]= tempCount*2;
graph[i][j] = 0;
tempCount = 0;
}
else{
tempCount = graph[i][j];
graph[i][j] = 0;
graph[curPoint--][j]= tempCount;
}
}
}
}
static void top() {
for (int j = 0; j < n; j++) {
int curPoint=0;
int tempCount = 0;
for (int i = 0; i < n; i++) {
if(graph[i][j] ==0) continue;
if(graph[i][j]==tempCount) {
graph[curPoint-1][j]= tempCount*2;
graph[i][j] = 0;
tempCount = 0;
}
else{
tempCount = graph[i][j];
graph[i][j] = 0;
graph[curPoint++][j]= tempCount;
}
}
}
}
static int[][] deepCopy(int[][] temp, int[][] graph){
for (int i = 0; i < temp.length; i++) {
temp[i] = graph[i].clone();
}
return temp;
}
static void print(int[][] graph) {
for (int[] is : graph) {
System.out.println(Arrays.toString(is));
}
System.out.println();
}
}
https://github.com/dydwkd486/coding_test/blob/main/baekjoon/java/baekjoon12094/Main.java
GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리
코딩테스트 공부한 내용 정리. Contribute to dydwkd486/coding_test development by creating an account on GitHub.
github.com
'Coding Test > baekjoon' 카테고리의 다른 글
| [백준 11048] 이동하기- python (solved.ac - 실버 1) (0) | 2022.09.06 |
|---|---|
| [백준 17135] 캐슬 디펜스- JAVA (solved.ac - 골드 3) (0) | 2022.08.20 |
| [백준 12100] 2048 (Easy)- JAVA (solved.ac - 골드 2) (0) | 2022.08.20 |
| [백준 3109] 빵집- JAVA (solved.ac - 골드 2) (0) | 2022.08.18 |
| [백준 1946] 신입 사원- JAVA (solved.ac - 실버 1) (0) | 2022.08.17 |