C# 백준 12100 2048 (Easy) (백트래킹, 브루트포스)

12100번: 2048 (Easy)

IDEA

브루트포스 문제는 복잡한 생각을 할 필요가 없어서 좋다. 한 때 재밌게 하던 2048 게임을 구현하는 문제다. 모든 가능성을 탐색해서 원하는 결과를 뽑아내면 된다. 탐색 과정에서 이전 과정을 기억해두고 되돌아가 다른 경로를 탐색할 수 있도록 하는 것이 관건이다. N * N 크기의 배열을 스택에 담아 탐색 과정을 관리하도록 했다. 

 

처음에는 N * N 배열을 매개변수로 하는 재귀 호출로 구현했다. 그런데 매개변수로 받아온 데이터는 참조 형식이라서 메소드 안에서 따로 돌아가는 것처럼 보여도 원본을 훼손하게 된다. 백트래킹의 핵심인 이전 과정 기억이 기능하지 않기 때문에 따로 메소드 진입 후에 새로운 배열을 선언하고 매개변수의 값을 복사해 새로운 배열의 값을 처리하는 방식으로 다시 코드를 짰다. 디버깅을 하다 보니까 너무 알아보기 어렵고 무슨 과정을 얘가 처리하고 있는지 이해가 안 돼서 아예 스택을 사용하기로 했다.

 

백트래킹은 깊이우선탐색과 결이 같고 깊이우선탐색은 스택의 원리를 이용하기 때문에 좀 더 직관적으로 코드를 짤 수 있었다.

 

1. 첫 입력을 받은 후 배열을 스택에 삽입한다.

2. 스택의 맨 위 데이터로 탐색을 시작한다.

3. 탐색 깊이가 5가 됐다면 스택의 데이터 하나를 삭제하고 현재 탐색을 탈출한다.

4. 상하좌우 방향으로 각각 블록을 밀고 스택에 배열을 삽입한다. (상하좌우로 탐색이 끝났다면 6을 실행)

5. 2로 돌아간다.

6. 스택의 데이터 하나를 삭제한다.

 

CODE

using System;
using System.Collections.Generic;
public class Board
{
	public int[,] board;
	// 필드는 은닉성을 유지해야하지만
	// 2차원의 필드는 get, set 키워드를 어떻게 써야
	// 속성으로 값을 주고 받을 수 있을지 고민하다가
	// 결국 public으로 간단히 포기했다.
	public Board(int N)
    {
		board = new int[N, N];
    }
}
class Program
{
	static int N, max;
	static Queue<int> blockpush = new Queue<int>();
	// 블록을 밀어낼 때 사용할 큐다.

	static Stack<Board> tracking = new Stack<Board>();
	// 탐색 과정을 기억할 스택
	enum Direction { right, down, left, up };

	static void Main()
	{
		N = int.Parse(Console.ReadLine());
		max = 0;
		Board first = new Board(N);
		for (int i = 0; i < N; i++)
		{
			var row = Console.ReadLine().Split();
			for (int j = 0; j < N; j++)
			{
				first.board[i, j] = int.Parse(row[j]);
				if (max < first.board[i, j])
					max = first.board[i, j];
			}
		}
		tracking.Push(first);
		// 게임의 최초상태를 스택에 삽입한다.

		Move(first.board, 0);
		Console.WriteLine(max);
	}

	static void Move(int[,] board, int depth)
	{
		if (depth == 5)
		{
			tracking.Pop();
			return;
		}	// 탐색 깊이가 5가 되었다면 스택을 하나 삭제하고 탈출

		Move(Push(Direction.right), depth + 1);
		Move(Push(Direction.down), depth + 1);
		Move(Push(Direction.left), depth + 1);
		Move(Push(Direction.up), depth + 1);
		// 상하좌우로 각각 한번씩 재귀호출한다.

		tracking.Pop();
		// 모든 방향 탐색이 끝났다면 스택을 하나 삭제하고 탈출
	}

	static int[,] Push(Direction dir)
	{
		Board push = new Board(N);
		// 새로운 배열을 만든다.
		switch(dir)
		{
			case Direction.right:
				for (int i = 0; i < N; i++)
				{
					for (int j = N - 1; j >= 0; j--)
						if (tracking.Peek().board[i, j] > 0)
							blockpush.Enqueue(tracking.Peek().board[i, j]);
					// 블록의 숫자들을 큐에 삽입한다.
					// 어차피 모든 블록을 공백없이 한 방향으로 쭉 밀어야하기 때문에
					// 0이 아닌 값만 FIFO 으로 불러오면 된다.

					for (int j = N - 1; j >= 0 && blockpush.Count > 0; j--)
					{
						if (push.board[i, j] == 0) push.board[i, j] = blockpush.Dequeue();
						// 큐가 비어있지 않은데 지금 보는 칸이 비었다면
						// 큐의 값을 불러온다.

						if (blockpush.Count == 0) break;
						// 큐가 비었다면 반복을 멈춘다.

						if (push.board[i, j] == blockpush.Peek())
							push.board[i, j] += blockpush.Dequeue();
						// 지금 보는 칸의 숫자와 큐의 맨 윗 값이 같다면
						// 큐에서 하나 더 꺼내오고 지금 보는 칸에 더해준다.

						// 이 방법으로 한 번 밀어줄 때 최대 2개의 블록만
						// 합쳐지도록 구현했다.
					}
				}
				break;
			case Direction.down:
				for (int j = 0; j < N; j++)
				{
					for (int i = N - 1; i >= 0; i--)
						if (tracking.Peek().board[i, j] > 0)
							blockpush.Enqueue(tracking.Peek().board[i, j]);
					for (int i = N - 1; i >= 0 && blockpush.Count > 0; i--)
					{
						if (push.board[i, j] == 0) push.board[i, j] = blockpush.Dequeue();
						if (blockpush.Count == 0) break;
						if (push.board[i, j] == blockpush.Peek())
							push.board[i, j] += blockpush.Dequeue();
					}
				}
				break;
			case Direction.left:
				for (int i = 0; i < N; i++)
				{
					for (int j = 0; j < N; j++)
						if (tracking.Peek().board[i, j] > 0)
							blockpush.Enqueue(tracking.Peek().board[i, j]);
					for (int j = 0; j < N && blockpush.Count > 0; j++)
					{
						if (push.board[i, j] == 0) push.board[i, j] = blockpush.Dequeue();
						if (blockpush.Count == 0) break;
						if (push.board[i, j] == blockpush.Peek())
							push.board[i, j] += blockpush.Dequeue();
					}
				}
				break;
			case Direction.up:
				for (int j = 0; j < N; j++)
				{
					for (int i = 0; i < N; i++)
						if (tracking.Peek().board[i, j] > 0)
							blockpush.Enqueue(tracking.Peek().board[i, j]);
					for (int i = 0; i < N && blockpush.Count > 0; i++)
					{
						if (push.board[i, j] == 0) push.board[i, j] = blockpush.Dequeue();
						if (blockpush.Count == 0) break;
						if (push.board[i, j] == blockpush.Peek())
							push.board[i, j] += blockpush.Dequeue();
					}
				}
				break;
		}
		for(int i = 0; i < N; i++)
        {
			for (int j = 0; j < N; j++)
				if (max < push.board[i, j]) max = push.board[i, j];
        }
		tracking.Push(push);
		// 새로 만들어진 배열을 스택에 삽입한다.

		return push.board;
	}
}