[SWEA] 6109번 자바(Java) 추억의 2048게임

풀이

  백준의 2048문제와 다르게 상하좌우중에 한 방향으로 한번만 이동하면 되는 문제이다. 따라서 100개 케이스 2초 즉 1케이스당 200만 복잡도까지 사용가능하다.

 

  방향을 입력받고 각 방향에 맞게 블럭을 이동시켜주면 된다. 이 과정을 투포인터로 할수도 있고  Queue를 사용할 수도 있다. 본인은 Deque을 사용해서 해당블록들이 합해지는 기록을 했다. 아래 이미지는 첫번째 케이스의 첫 열이 Queue에 들어오는과정을 설명한다. 중요한점은 3가지 조건을 생각해야한다.

1. Queue가 비어있는가? -> 비어있다면 해당 칸값 바로 추가
2. 칸의 값이 0인가? -> 추가X
3. 바로 이전에 값이 합쳐졌는가?(이 조건을 안넣으면 계속해서 칸의 합이 합쳐진다.) -> 다음칸은 그냥 Queue에 추가

초기 2048 Map

Deque이 비어있고 칸의 값이 0이 아니므로 deque에 추가

칸의 값이 0아니고 deque의 pollLast값인 4와 칸의값 4가 동일하므로 8로 합쳐준다+ 추가로 flag는 true로 둬서 다음값이 합쳐지지않게 한다

 

칸의 값이 0이아니고 flag가 true였으므로 값추가, 그리고 이제 더할수있으니까 flag=false로 변경

 

칸의 값이 0이 아니고 flag=false라서 더할수 있지만 8 != 2라서 그냥 추가

 

이후에는 Queue에서 순차적으로 값을 뽑아서 map해당열의 0 ~ N-1까지 칸을 다시 채워준다

 

 

이제 각 방향에 맞게 파라미터만 변경해서 진행하면 된다.

공통된 코드가 많아서 이걸 하나의 메서드로 줄일 수 있다. 이를 위해 고려할점은 2가지이다.

1. 이동방향: 상하, 좌우
2. 이동크기: 1, -1

이를 고려해서 코드를 짜게될때 파라미터로 (방향, 시작 index, 끝 index, 이동크기)를 줘야한다.

이렇게 코드를 짜면 4개 방향을 한 메서드로 구현할 수 있다.

 

 

예제 입력 예시

2
5 up     //테스트케이스 개수
4 8 2 4 0  //첫 번째 테스트 케이스, N = 5
4 4 2 0 8
8 0 2 4 4
2 2 2 2 8
0 2 2 0 0
2 down //두 번째 테스트 케이스, N = 2
16 2
0 2

 

예제 출력 예시

#1  //첫번째 테스트 케이스
8 8 4 8 8
8 4 4 2 4
2 4 2 0 8
0 0 0 0 0
0 0 0 0 0
#2 //두번째 테스트 케이스
0 0
16 4

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Solution {
	private static int N;
	private static int[][] map;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		for (int t = 0; t < T; t++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			String di = st.nextToken();

			// map입력받기
			map = new int[N][N];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			sb.append("#").append(t + 1).append("\n");
			if (di.equals("up")) play2048(false, 0, N, 1);
			else if(di.equals("down")) play2048(false, N-1, -1, -1);				
			else if(di.equals("right")) play2048(true, N-1, -1, -1);
			else play2048(true, 0, N, 1);
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					sb.append(map[i][j]).append(" ");
				}
				sb.append("\n");
			}
		}
		System.out.println(sb);
	}

	private static void play2048(boolean goX, int s, int e, int m) {
		int ys = 0;
		int xs = 0;
		if(goX)xs = s;
		else ys = s;
		
		while(!((goX)? ys == N: xs == N)) {
			Deque<Integer> d = new LinkedList<>();
			boolean flag = false; //true면 이전에서 합쳐진경우
			if(goX) xs = s; 
			else ys = s;
			
			while(!((goX)? xs == e: ys == e)) {
				if(map[ys][xs] == 0) {}
				else if(d.isEmpty()) d.add(map[ys][xs]); // 비어있는 경우
				else if(flag||d.peekLast() != map[ys][xs]) { // 이전에서 합쳐진 경우 또는 현개값과 스택의 peek이 다른경우 
					d.add(map[ys][xs]);
					flag = false;
				}
				else if(map[ys][xs] != 0){ //flag가 false이고 같은 경우
					d.add(d.pollLast()*2);
					flag = true;
				}
				map[ys][xs] = 0;
				if(goX) xs+=m;
				else ys+=m;
			}					
			
			//빈칸 채워주기
			if(goX) { 
				int xIdx = s;
				while(!d.isEmpty()){
					map[ys][xIdx] = d.poll();
					xIdx+=m;
				}
				ys++; 
			}
			else{
				int yIdx = s;
				while(!d.isEmpty()){
					map[yIdx][xs] = d.poll();
					yIdx+=m;
				}
				xs++;
			}
		}
	}
}