[SWEA/Java] 추억의 2048 게임(6190)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWbrg9uabZsDFAWQ

SW Expert Academy

1. 문제 분석

문제 개요:
2048 게임에서 보드의 숫자들을 이동시키고 합치는 문제입니다. 주어진 방향(왼쪽, 오른쪽, 위, 아래)으로 모든 숫자들을 이동시키고 합쳐야 합니다. 각 숫자는 같은 숫자와 합쳐지며, 합쳐진 숫자는 이동 후 새로운 숫자가 됩니다.

입력 형식:

1. 첫 줄에 테스트 케이스의 수 T가 주어진다.
2. 각 테스트 케이스는 다음과 같은 형식이다.
   • 첫 줄에 보드의 크기 N과 이동 방향이 주어진다.
   • 다음 N줄에 보드의 상태가 주어진다. 각 줄은 N개의 정수로 구성된다.

출력 형식:

• 각 테스트 케이스에 대해, 이동 후의 보드를 출력한다.

2. 알고리즘 종류

해당 문제는 "구현 및 시뮬레이션" 문제입니다. 각 방향에 대해 다음과 같은 작업을 수행합니다:

• 왼쪽: 숫자를 왼쪽으로 이동시키고 합칩니다.
• 오른쪽: 숫자를 오른쪽으로 이동시키고 합칩니다.
• 위쪽: 숫자를 위쪽으로 이동시키고 합칩니다.
• 아래쪽: 숫자를 아래쪽으로 이동시키고 합칩니다.

이 문제는 큐(Queue) 및 스택(Stack) 을 사용하여 구현됩니다. 각 방향에 따라 숫자들을 큐 또는 스택에 저장하고, 이를 통해 숫자들을 이동시키고 합치는 작업을 수행합니다.

3. 주요 부분 및 코드 작성 방법

1. 방향 처리:

• 각 방향(왼쪽, 오른쪽, 위, 아래)에 대해 별도의 메서드를 작성하여 처리합니다.

2. 큐와 스택의 사용:

• 왼쪽 및 위쪽: Queue를 사용하여 숫자를 왼쪽 또는 위쪽으로 이동시키며, 숫자가 같은 경우 합칩니다.
• 오른쪽 및 아래쪽: Stack을 사용하여 숫자를 오른쪽 또는 아래쪽으로 이동시키며, 숫자가 같은 경우 합칩니다.

3. left() 메서드:

• 각 줄의 숫자를 큐에 추가하여 왼쪽으로 이동시키고 합칩니다.
• 큐를 이용해 숫자를 왼쪽으로 정렬하고 합칩니다.
• 최종 결과를 answer 배열에 저장합니다.

4. right() 메서드:

• 각 줄의 숫자를 스택에 추가하여 오른쪽으로 이동시키고 합칩니다.
• 스택을 사용해 숫자를 오른쪽으로 정렬하고 합칩니다.
• 최종 결과를 answer 배열에 저장합니다.

5. up() 메서드:

• 각 열의 숫자를 큐에 추가하여 위쪽으로 이동시키고 합칩니다.
• 큐를 이용해 숫자를 위쪽으로 정렬하고 합칩니다.
• 최종 결과를 answer 배열에 저장합니다.

6. down() 메서드:

• 각 열의 숫자를 스택에 추가하여 아래쪽으로 이동시키고 합칩니다.
• 스택을 사용해 숫자를 아래쪽으로 정렬하고 합칩니다.
• 최종 결과를 answer 배열에 저장합니다.

4. 코드 설명

왼쪽 이동 (left()):

public static void left() {
    Queue<Integer> q = new LinkedList<>();
    Queue<Integer> newQ = new LinkedList<>();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (Board[i][j] != 0) q.add(Board[i][j]);
        }
        while (!q.isEmpty()) {
            if (q.size() == 1) {
                newQ.add(q.poll());
                break;
            }
            int n = q.poll();
            if (n == q.peek()) {
                int sum = n + q.poll();
                newQ.add(sum);
            } else {
                newQ.add(n);
            }
        }
        int k = 0;
        while (!newQ.isEmpty()) {
            answer[i][k++] = newQ.poll();
        }
    }
}

• Queue를 사용하여 숫자들을 왼쪽으로 이동시키고, 같은 숫자는 합칩니다.
• 처리된 결과를 answer 배열에 저장합니다.

오른쪽 이동 (right()):

public static void right() {
    Stack<Integer> s = new Stack<>();
    Stack<Integer> newS = new Stack<>();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (Board[i][j] != 0) s.add(Board[i][j]);
        }
        while (!s.isEmpty()) {
            if (s.size() == 1) {
                newS.add(s.pop());
                break;
            }
            int n = s.pop();
            if (n == s.peek()) {
                int sum = n + s.pop();
                newS.add(sum);
            } else {
                newS.add(n);
            }
        }
        int k = 0;
        while (!newS.isEmpty()) {
            answer[i][N - newS.size()] = newS.pop();
        }
    }
}

• Stack을 사용하여 숫자들을 오른쪽으로 이동시키고, 같은 숫자는 합칩니다.
• 처리된 결과를 answer 배열에 저장합니다.

위쪽 이동 (up()):

public static void up() {
    Queue<Integer> q = new LinkedList<>();
    Queue<Integer> newQ = new LinkedList<>();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (Board[j][i] != 0) q.add(Board[j][i]);
        }
        while (!q.isEmpty()) {
            if (q.size() == 1) {
                newQ.add(q.poll());
                break;
            }
            int n = q.poll();
            if (n == q.peek()) {
                int sum = n + q.poll();
                newQ.add(sum);
            } else {
                newQ.add(n);
            }
        }
        int k = 0;
        while (!newQ.isEmpty()) {
            answer[k++][i] = newQ.poll();
        }
    }
}

• Queue를 사용하여 숫자들을 위쪽으로 이동시키고, 같은 숫자는 합칩니다.
• 처리된 결과를 answer 배열에 저장합니다.

아래쪽 이동 (down()):

public static void down() {
    Stack<Integer> s = new Stack<>();
    Stack<Integer> newS = new Stack<>();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (Board[j][i] != 0) s.add(Board[j][i]);
        }
        while (!s.isEmpty()) {
            if (s.size() == 1) {
                newS.add(s.pop());
                break;
            }
            int n = s.pop();
            if (n == s.peek()) {
                int sum = n + s.pop();
                newS.add(sum);
            } else {
                newS.add(n);
            }
        }
        int k = 0;
        while (!newS.isEmpty()) {
            answer[N - newS.size()][i] = newS.pop();
        }
    }
}

• Stack을 사용하여 숫자들을 아래쪽으로 이동시키고, 같은 숫자는 합칩니다.
• 처리된 결과를 answer 배열에 저장합니다.

---

5. 전체 코드

package SWEA6109_240821;

import java.io.*;
import java.util.*;

public class Solution {
	static int N;
	static int[][] Board, answer;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			String direction = st.nextToken();
			Board = new int[N][N];
			answer = new int[N][N];
			
			for(int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for(int j = 0; j < N; j++) Board[i][j] = Integer.parseInt(st.nextToken());
			}
			
			if(direction.equals("left")) left();
			else if(direction.equals("right")) right();
			else if(direction.equals("up")) up();
			else if(direction.equals("down")) down();

			System.out.println("#" + tc);
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) System.out.print(answer[i][j] + " ");
				System.out.println();
			}
		}
	}
	
	public static void left() {
		Queue<Integer> q = new LinkedList<>();
		Queue<Integer> newQ = new LinkedList<>();
		for(int i = 0; i < N; i++) { // 줄 별 계산
			int cnt = 0;
			for(int j = 0; j < N; j++) { // 각 줄의 숫자 q에 추가
				if(Board[i][j] != 0) q.add(Board[i][j]);
//				System.out.println(q);
			}
			while(!q.isEmpty()) { // q가 빌 때까지 반복
				if(q.size() == 1) {
					newQ.add(q.poll());
					break;
				}
				int n = q.poll();
				if(n == q.peek()) { // 같은 숫자를 만나면 
					int sum = n + q.poll();
					newQ.add(sum); // 합치기
				}
				else {
					newQ.add(n);
				}
			}
//			System.out.println("test : " + newQ);
			int k = 0;
			while(!newQ.isEmpty()) {
				answer[i][k++] = newQ.poll();
			}
		}
	}
	public static void right() {
		Stack<Integer> s = new Stack<>();
		Stack<Integer> newS = new Stack<>();
		for(int i = 0; i < N; i++) { // 줄 별 계산
			int cnt = 0;
			for(int j = 0; j < N; j++) { // 각 줄의 숫자 q에 추가
				if(Board[i][j] != 0) s.add(Board[i][j]);
//				System.out.println(s);
			}
			while(!s.isEmpty()) { // s가 빌 때까지 반복
				if(s.size() == 1) {
					newS.add(s.pop());
					break;
				}
				int n = s.pop();
				if(n == s.peek()) { // 같은 숫자를 만나면 
					int sum = n + s.pop();
					newS.add(sum); // 합치기
				}
				else {
					newS.add(n);
				}
			}
//			System.out.println("test : " + newS);
			int k = 0;
			while(!newS.isEmpty()) {
				answer[i][N - newS.size()] = newS.pop();
			}
		}
	}
	public static void up() {
		Queue<Integer> q = new LinkedList<>();
		Queue<Integer> newQ = new LinkedList<>();
		for(int i = 0; i < N; i++) { // 줄 별 계산
			int cnt = 0;
			for(int j = 0; j < N; j++) { // 각 줄의 숫자 q에 추가
				if(Board[j][i] != 0) q.add(Board[j][i]);
//				System.out.println(q);
			}
			while(!q.isEmpty()) { // q가 빌 때까지 반복
				if(q.size() == 1) {
					newQ.add(q.poll());
					break;
				}
				int n = q.poll();
				if(n == q.peek()) { // 같은 숫자를 만나면 
					int sum = n + q.poll();
					newQ.add(sum); // 합치기
				}
				else {
					newQ.add(n);
				}
			}
//			System.out.println("test : " + newQ);
			int k = 0;
			while(!newQ.isEmpty()) {
				answer[k++][i] = newQ.poll();
			}
		}
	}
	public static void down() {
		Stack<Integer> s = new Stack<>();
		Stack<Integer> newS = new Stack<>();
		for(int i = 0; i < N; i++) { // 줄 별 계산
			int cnt = 0;
			for(int j = 0; j < N; j++) { // 각 줄의 숫자 q에 추가
				if(Board[j][i] != 0) s.add(Board[j][i]);
//				System.out.println(s);
			}
			while(!s.isEmpty()) { // s가 빌 때까지 반복
				if(s.size() == 1) {
					newS.add(s.pop());
					break;
				}
				int n = s.pop();
				if(n == s.peek()) { // 같은 숫자를 만나면 
					int sum = n + s.pop();
					newS.add(sum); // 합치기
				}
				else {
					newS.add(n);
				}
			}
//			System.out.println("test : " + newS);
			int k = 0;
			while(!newS.isEmpty()) {
				answer[N - newS.size()][i] = newS.pop();
			}
		}
	}
}