[골드2] 12100. 2048 (Easy) (Java)

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 Easy,,,,?? 

---

※  문제를 요약하면 아래와 같습니다.

▶ 2048 게임은 혼자 즐기는 재미있는(?) 게임 => 게임 플레이  https://play2048.co/

▶ 해당 게임에서의 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동 시키는 것

▶ 이 때 블록이 충돌할 경우, 값이 같으면 해당 턴에 딱 1번만 겹쳐지며 값이 2배로 변경

▶ 이 때 블록이 충돌할 경우, 값이 같으면 블럭이 모두 움직인 한 턴에 딱 1번만 겹쳐지며,

         이미 1번 겹쳤을 경우 해당 턴에는 더이상 겹쳐지지 않는다.

▶ NxN 크기의 보드가 주어 질 때 최대 5번 이동해서 만들 수 있는 블록의 최댓값 구하기

▶ Input : 첫째 줄에 보드의 크기 N 입력, 둘째 줄 부터 N개의 줄만큼 초기 보드의 값이 입력

▶ Output : 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록값 출력

---

◈ Input - 1

3
2 2 2
4 4 4
8 8 8

◈ Output - 1

16

◈ Input - 2

20
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024

◈ Output - 2

32768

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ BFS 로 최대 5번의 경우의 수 탐색

▶ 탐색을 위해 해당 맵의 상태를 저장한 2차원 배열과 탐색 횟수를 저장한 GameMap 클래스 구현 

▶ 2차원 배열을 클래스에 저장하고, BFS 큐에 넣는 과정에서 깊은 복사 필수

    = > 깊은 복사를 하지 않으면 메모리에서 배열들이 이어져 있게 되며,  다른 bfs 방향에서 배열값을 변경했을 경우에도

         현재 탐색을 진행하고 있는 배열 값이 변경이 됩니다아

▶ BFS 과정에서 델타 탐색을 활용, 동, 서, 남, 북 방향으로 블록값을 이동

     이 때 탐색하는 방향에서 가까운 쪽의 배열값 부터 블록값을 이동

     ex) 동쪽 방향 탐색 시 배열의 가장 오른쪽에 있는 블록 부터 이동 ( 코드 내 Moving 함수 참조 ) 

▶ 블록이 인덱스 범위를 벗어나거나 다른 블록과 충돌하기 전까지 해당 방향으로 이동

▶ 블록 충돌 시 값이 동일하면 합쳐주고 값을 2배로 적용  ( 코드 내 Doing 함수 참조 )

     만약, 해당 턴에 이미 값이 2배로 적용된 블록과 충돌할 경우 블록을 합치지 않는다.

▶ 블록을 5번 움직였을 때 배열 안의 Max값을 비교하여 블록의 최대값 저장

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class GameMap {
	int[][] m_narrTemp;
	int m_nCount;

	public GameMap() {
		// TODO Auto-generated constructor stub
	}

	public GameMap(int[][] m_narrTemp, int m_nCount) {
		this.m_narrTemp = m_narrTemp;
		this.m_nCount = m_nCount;
	}
}

public class Main {

	static int N;
	static int[][] narrMap;
	static boolean[][] barrVisit;
	static int nMax;

	// 델타 탐색
	static int dr[] = { 0, 0, 1, -1 };
	static int dc[] = { 1, -1, 0, 0 };

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(bReader.readLine());

		narrMap = new int[N][N];

		// 맵 정보 입력 받자
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(bReader.readLine());
			for (int j = 0; j < N; j++) {
				narrMap[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		nMax = 2;
		// BFS 탐색을 통해 게임에서 가능한 모든 경우의 수를 돌려보자
		BFS_2048();

		bWriter.write(String.valueOf(nMax));
		bWriter.close();
	}

	private static void BFS_2048() {
		Queue<GameMap> queueBFS = new LinkedList<>();

		queueBFS.add(new GameMap(narrMap, 0));

		// 탐색 돌리자아
		while (!queueBFS.isEmpty()) {
			GameMap temp = queueBFS.poll();

			// 5번에 도달했으니 sum을 갖고 와서 max와 비교
			if (temp.m_nCount == 5) {
				int nSum = getVal(temp.m_narrTemp);
				if (nMax < nSum) {
					nMax = nSum;
				}

				continue;
			}

			int[][] narrCopy = new int[N][N];
			// 깊은 복사 해야해 아마두,,?
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++)
					narrCopy[i][j] = temp.m_narrTemp[i][j];
			}

			// 블록을 움직이자
			for (int k = 0; k < dr.length; k++) {
				// 맵의 결과가 똑같으면 더 이상 탐색을 진행 하지 않는다.
				// System.out.println(temp.m_nCount + " <<<<< 카운트 ");
				int[][] narrResult = new int[N][N];
				
				// 깊은 복사 해야해 델타 돌때마다,, 극혐,,
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++)
						narrResult[i][j] = narrCopy[i][j];
				}
				// 무빙 또 보고싶다
				if (Moving(narrResult, k)) {
					queueBFS.add(new GameMap(narrResult, temp.m_nCount + 1));
				} else {
					// 더 이상 이 블록은 탐색하지 않으니 Max값을 저장해두자
					int nSum = getVal(temp.m_narrTemp);

					if (nMax < nSum) {
						nMax = nSum;
					}
				}
			}

		}
	}

	private static boolean Moving(int[][] narrCopy, int nDirection) {
		// 북쪽이면 0~N-1
		// 남쪽이면 N-1~0
		// 서쪽이면 0~N-1
		// 동쪽이면 N-1~0
		barrVisit = new boolean[N][N];
		boolean bFind = false;
		// 동쪽 방향
		if (nDirection == 0) {
			for (int i = 0; i < N; i++) {
				for (int j = N - 1; j >= 0; j--) {
					// 블록을 찾으면 ?
					if (narrCopy[i][j] > 0) {
						boolean bResult = Doing(i, j, nDirection, narrCopy);
						// 블록이 움직였으므로 true로 바꿔준다
						if (!bFind && bResult)
							bFind = true;
					}
				}
			}
		}
		// 서쪽 방향
		if (nDirection == 1) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					// 블록을 찾으면 ?
					if (narrCopy[i][j] > 0) {
						boolean bResult = Doing(i, j, nDirection, narrCopy);
						// 블록이 움직였으므로 true로 바꿔준다
						if (!bFind && bResult)
							bFind = true;
					}
				}
			}
		}
		// 남쪽 방향
		if (nDirection == 2) {
      
			for (int i = N - 1; i >= 0; i--) {
				for (int j = 0; j < N; j++) {
					// 블록을 찾으면 ?
					
					if (narrCopy[i][j] > 0) {
						boolean bResult = Doing(i, j, nDirection, narrCopy);
						// 블록이 움직였으므로 true로 바꿔준다
						if (!bFind && bResult)
							bFind = true;
					}
				}
			}
		}
		// 북쪽 방향
		if (nDirection == 3) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					// 블록을 찾으면 ?
					if (narrCopy[i][j] > 0) {
						boolean bResult = Doing(i, j, nDirection, narrCopy);
						// 블록이 움직였으므로 true로 바꿔준다
						if (!bFind && bResult)
							bFind = true;
					}
				}
			}
		}

		return bFind;
	}

	// 배열 안의 최댓값을 리턴하자
	public static int getVal(int[][] narrTemp) {
		int nMaxTemp = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++)
				nMaxTemp = Math.max(nMaxTemp, narrTemp[i][j]);
		}

		return nMaxTemp;
	}

	// 블록을 움직이자
	public static boolean Doing(int i, int j, int nDirection, int[][] narrCopy) {
		int nSearchRow = i;
		int nSearchCol = j;
		// 한번 합쳐졌는지 체크 해볼 배열
		// 다른 블럭 or 배열 외곽에 도달할 때 까지
		boolean bFind = false;
		while (nSearchRow >= 0) {

			nSearchRow += dr[nDirection];
			nSearchCol += dc[nDirection];

			// 범위 체크
			if (nSearchRow < 0 || nSearchCol < 0 || nSearchRow >= N || nSearchCol >= N) {

				nSearchRow -= dr[nDirection];
				nSearchCol -= dc[nDirection];

				// 맵 정보 변경
				int nTemp = narrCopy[i][j];
				narrCopy[i][j] = 0;
				narrCopy[nSearchRow][nSearchCol] = nTemp;

				break;
			}
			
			// 앞에 블록이 있는데
			if (narrCopy[nSearchRow][nSearchCol] > 0) {

				int nNowRow = nSearchRow - dr[nDirection];
				int nNowCol = nSearchCol - dc[nDirection];
				// 숫자가 같다 ???
				if (narrCopy[i][j] == narrCopy[nSearchRow][nSearchCol]
						&& !barrVisit[nSearchRow][nSearchCol]) {
					barrVisit[nSearchRow][nSearchCol] = true;

					// 맵정보 변경 -> 블록 합치기
					narrCopy[nSearchRow][nSearchCol] *= 2;
					narrCopy[i][j] = 0;
					
					if(!bFind)
						bFind = true;
				} else {
					// 이미 방문했거나 숫자가 같지 않다
					int nTemp = narrCopy[i][j];
					narrCopy[i][j] = 0;
					narrCopy[nNowRow][nNowCol] = nTemp;
				}
				break;
			}
			if(!bFind)
				bFind = true;
		}
		
		return bFind;
	}

}

---

Good Luck! (피드백 감사합니다!)