https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
문제접근방법
1. 5번을 어떤방식으로 만들어서 전해줄것인가 -> 순열, 조합, 부분집합으로 도저히 생각이 안나서 5중포문 사용했다.
2. 그 뒤로는 게임방식을 이해하면서 코드를 짜면서 자잘한 오류들을 수정함
3. 상하, 좌우 묶어서 생각하니까 훨씬 편했다.
도움된테스트케이스
1번
3
2 0 2
0 2 0
2 0 2
답은 4가 나와야 하는데
8이 나와서 이부분에서 잘못된부분을 바로잡음
최대로 이동하고 숫자를 만나지 못한경우에서
아래 예시에서
2 0 0
0 0 0
0 0 0
comp가 1일때
temp[i][j+comp-1] = temp[i][j];
temp[i][j] = 0;
위와같은 경우에서 위로 이동이 안돼고
2가 삭제되는 경우가 발생해서
if(j+comp-1==j) break;
else {
temp[i][j+comp-1] = temp[i][j];
temp[i][j] = 0;
break;
}
이렇게 수정함
2번
2 2 4 16
이 상황에서 <- 좌측으로 이동시
4 4 16 0 이 되어야 정상인데
8 16 0 0 이 되서 한번 합쳐지고 나면
방문체크를 통해서 다시 합쳐지지 않게 고치고 방식으로 수정했음
힘들었던 부분
5중 포문을 해결하는 방법은 재귀를 통해 순열을 생성할때 중복체크를 하지않으면 가능하다는 부분을 알게 되었다.
이부분이 생각이 안나서 문제 코딩하기전에 이부분만 계속 생각해봤던것 같다.
막상 5중포문으로라도 바로 풀고 잘푼 사람 코드를 봤으면 더 좋았을것 같다는 생각
import java.io.*;
import java.util.*;
public class Main {
static int N,map[][],res;
static boolean checked[][];
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stz;
N = Integer.parseInt(br.readLine());
map = new int[N][N];
res =0;
for(int i=0;i<N;i++) {
stz = new StringTokenizer(br.readLine()," ");
for(int j=0;j<N;j++) {
map[i][j]= Integer.parseInt(stz.nextToken());
}
}
for(int i=0;i<4;i++) {
for(int j=0;j<4;j++) {
for(int k=0;k<4;k++) {
for(int l=0;l<4;l++) {
for(int q=0;q<4;q++) {
mover(new int[] {i,j,k,l,q});
}
}
}
}
}
System.out.println(res);
}
// 0123 상하좌우
static int [][] temp;
private static void mover(int[] dir) {
int val = 0;
temp =new int[N][N];
for(int i=0;i<N;i++) temp[i] = Arrays.copyOf(map[i], N);
for(int i=0;i<5;i++) {
if(dir[i]==0) {
top(temp);
}else if(dir[i]==1) {
bottom(temp);
}else if(dir[i]==2) {
left(temp);
}else if(dir[i]==3) {
right(temp);
}
}
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
if(val<temp[i][j]) {
val =temp[i][j];
}
}
}
res = Math.max(val, res);
}
private static void right(int[][] temp) {
int comp;
checked =new boolean[N][N];
for(int i=0;i<N;i++) {
for(int j=N-2;j>=0;j--) {
// 영이면 무시
if(temp[i][j]==0) continue;
// 영이 아닌 숫자라면 이동 준비
else {
// 숫자를 만날떄 까지 전진 but 0까지만
// 만났을때 같으면 더함 다름 면 정지
comp = 1;
while(true) {
if(j+comp<N) {
if(temp[i][j+comp]==0) {
//0만나면 한칸더 전진
comp++;
continue;
}else {
// 숫자를 만나면 같은가 비교
// 같으면 더함 다르면 전칸으로 이동 후 종료
if(temp[i][j+comp]==temp[i][j] && !checked[i][j+comp]) {
checked[i][j+comp] = true;
temp[i][j+comp] += temp[i][j];
temp[i][j] = 0;
break;
}else {
//수가 다르면
if(j+comp-1==j) break;
else {
temp[i][j+comp-1] = temp[i][j];
temp[i][j] = 0;
break;
}
}
}
}else {
//최대로 전진했다면
if(j+comp-1==j) break;
else {
temp[i][j+comp-1] = temp[i][j];
temp[i][j] = 0;
break;
}
}
}
}
}
}
}
private static void left(int[][] temp) {
int comp;
checked =new boolean[N][N];
for(int i=0;i<N;i++) {
for(int j=1;j<N;j++) {
// 영이면 무시
if(temp[i][j]==0) continue;
// 영이 아닌 숫자라면 이동 준비
else {
// 숫자를 만날떄 까지 전진 but 0까지만
// 만났을때 같으면 더함 다름 면 정지
comp = 1;
while(true) {
if(j-comp>=0) {
if(temp[i][j-comp]==0) {
//0만나면 한칸더 전진
comp++;
continue;
}else {
// 숫자를 만나면 같은가 비교
// 같으면 더함 다르면 전칸으로 이동 후 종료
if(temp[i][j-comp]==temp[i][j] && !checked[i][j-comp]) {
checked[i][j-comp] =true;
temp[i][j-comp] += temp[i][j];
temp[i][j] = 0;
break;
}else {
//수가 다르면
if(j-comp+1==j) break;
else {
temp[i][j-comp+1] = temp[i][j];
temp[i][j] = 0;
break;
}
}
}
}else {
//최대로 전진했다면
if(j-comp+1==j) break;
else {
temp[i][j-comp+1] = temp[i][j];
temp[i][j] = 0;
break;
}
}
}
}
}
}
}
private static void bottom(int[][] temp) {
int comp;
checked =new boolean[N][N];
for(int i=N-2;i>=0;i--) {
for(int j=0;j<N;j++) {
// 영이면 무시
if(temp[i][j]==0) continue;
// 영이 아닌 숫자라면 이동 준비
else {
// 숫자를 만날떄 까지 전진 but 0까지만
// 만났을때 같으면 더함 다름 면 정지
comp = 1;
while(true) {
if(i+comp<N) {
if(temp[i+comp][j]==0) {
//0만나면 한칸더 전진
comp++;
continue;
}else {
// 숫자를 만나면 같은가 비교
// 같으면 더함 다르면 전칸으로 이동 후 종료
if(temp[i+comp][j]==temp[i][j] && !checked[i+comp][j]) {
checked[i+comp][j] = true;
temp[i+comp][j] += temp[i][j];
temp[i][j] = 0;
break;
}else {
//수가 다르면
if(i+comp-1==i) break;
else {
temp[i+comp-1][j] = temp[i][j];
temp[i][j] = 0;
break;
}
}
}
}else {
//최대로 전진했다면
if(i+comp-1==i) break;
else {
temp[i+comp-1][j] = temp[i][j];
temp[i][j] = 0;
break;
}
}
}
}
}
}
}
private static void top(int[][] temp) {
int comp;
checked =new boolean[N][N];
for(int i=1;i<N;i++) {
for(int j=0;j<N;j++) {
// 영이면 무시
if(temp[i][j]==0) continue;
// 영이 아닌 숫자라면 이동 준비
else {
// 숫자를 만날떄 까지 전진 but 0까지만
// 만났을때 같으면 더함 다름 면 정지
comp = 1;
while(true) {
if(i-comp>=0) {
if(temp[i-comp][j]==0) {
//0만나면 한칸더 전진
comp++;
continue;
}else {
// 숫자를 만나면 같은가 비교
// 같으면 더함 다르면 전칸으로 이동 후 종료
if(temp[i-comp][j]==temp[i][j] && !checked[i-comp][j]) {
checked[i-comp][j] =true;
temp[i-comp][j] += temp[i][j];
temp[i][j] = 0;
break;
}else {
//수가 다르면
if(i-comp+1==i) break;
else {
temp[i-comp+1][j] = temp[i][j];
temp[i][j] = 0;
break;
}
}
}
}else {
//최대로 전진했다면
if(i-comp+1==i) break;
else {
temp[i-comp+1][j] = temp[i][j];
temp[i][j] = 0;
break;
}
}
}
}
}
}
}
}
'acmicpc > Java' 카테고리의 다른 글
| [Java] 백준 19236 청소년 상어 (0) | 2022.04.07 |
|---|---|
| [JAVA] 백준 11559 뿌요뿌요 Puyo Puyo (0) | 2022.04.06 |
| [JAVA] 백준 1929 소수 구하기 (0) | 2022.03.28 |
| [JAVA] 17404 RGB거리 2 (0) | 2022.03.27 |
| [Java] 백준 2164 카드2 (0) | 2022.03.27 |
댓글