[BOJ][C#] 12100 2048 (Easy)

LimJaeJun·2023년 9월 29일

PS/BOJ

목록 보기

31/108

📕 문제

📗 접근 방식

각 타일은 Point 클래스로 표현되며, Board 클래스에 배치(클래스화 하여 풀려고 노력함)
DFS (깊이 우선 탐색)를 활용하여 모든 가능한 움직임 조합을 시도
각 움직임 조합마다 보드를 업데이트하고 최대 블록 값을 계산
모든 움직임 조합을 시도하고 난 후 최대 블록 값을 출력

중요한 접근 방식
한 방향을 결정 (상하좌우 상관없음, 본인 상으로 결정)
그렇다면 선택한 방향을 제외한 방향을 어떻게 구현할 것인가?

만약 아래로 가고 싶다면 전체 매트릭스(Board)를 180도 회전하여 위로 이동한다면 결국 아래로 이동한 것이다. 이와 마찬가지로 회전과 이동을 통해 상하좌우를 모두 구현할 수 있다.

또한, 위로 이동하는 로직을 한 column만 구현한다면 모든 column에 대해 실행한다면 결국 위로 이동하는 로직을 구현한 것이다.

자세한 로직은 아래 코드를 보면 이해할 수 있을 것이다.

📘 코드

namespace BOJ
{
    class No_12100
    {
        public class Point
        {
            private int pointValue;

            public bool IsActivated => pointValue == 0 ? false : true;

            public int Value
            {
                get => pointValue;
                set => pointValue = value;
            }

            public Point(int value)
            {
                pointValue = value;
            }

            public void Combine(Point other)
            {
                pointValue <<= 1;
                other.Clear();
            }

            public void Clear()
            {
                pointValue = 0;
            }
        }

        public class Board
        {
            private Point[,] mainBoard;

            public Board(int num)
            {
                mainBoard = new Point[num, num];
            }

            public void SetPointValue(int x, int y, int value) => mainBoard[x, y] = new Point(value);
            public int GetPointValue(int x, int y) => mainBoard[x, y].Value;

            private void MoveUpRow(int rowIndex)
            {
                for(int i = 0 ; i < n ; i++)
                {
                    if(!mainBoard[i, rowIndex].IsActivated) continue;

                    for(int j = i + 1 ; j < n ; j++)
                    {
                        if(!mainBoard[j, rowIndex].IsActivated) continue;

                        if(mainBoard[i, rowIndex].Value == mainBoard[j, rowIndex].Value)
                        {
                            mainBoard[i, rowIndex].Combine(mainBoard[j, rowIndex]);
                        }
                        else
                        {
                            i = j - 1;
                        }
                        break;
                    }
                }

                for(int i = 0 ; i < n ; i++)
                {
                    if(mainBoard[i, rowIndex].IsActivated)
                    {
                        int j = i - 1;
                        while(j >= 0 && !mainBoard[j, rowIndex].IsActivated)
                        {
                            mainBoard[j, rowIndex].Value = mainBoard[j + 1, rowIndex].Value;
                            mainBoard[j + 1, rowIndex].Clear();
                            j--;
                        }
                    }
                }
            }

            public void MoveUp()
            {
                for(int i = 0 ; i < n ; i++)
                {
                    MoveUpRow(i);
                }
            }

            public void Rotate()
            {
                Point[,] tempBoard = new Point[n, n];

                for(int x = 0 ; x < n ; x++)
                {
                    for(int y = 0 ; y < n ; y++)
                    {
                        tempBoard[x, y] = mainBoard[y, n - x - 1];
                    }
                }

                mainBoard = tempBoard;
            }

            public int FindMaxPoint()
            {
                int maxBlock = 0;
                for(int i = 0 ; i < n ; i++)
                {
                    for(int j = 0 ; j < n ; j++)
                    {
                        maxBlock = Math.Max(maxBlock, mainBoard[i, j].Value);
                    }
                }
                return maxBlock;
            }
        }

        const int MAX_MOVE_COUNT = 5;
        static int n;

        static void Main()
        {
            n = int.Parse(Console.ReadLine());
            Board board = new Board(n);

            for(int x = 0 ; x < n ; x++)
            {
                string[] row = Console.ReadLine().Split();
                for(int y = 0 ; y < n ; y++)
                {
                    int value = int.Parse(row[y]);
                    board.SetPointValue(x, y, value);
                }
            }

            int maxBlock = FindMaxValue(board, 0);
            Console.WriteLine(maxBlock);
        }

        static int FindMaxValue(Board board, int moveCount)
        {
            if(moveCount == MAX_MOVE_COUNT)
            {
                return board.FindMaxPoint();
            }

            int maxBlock = 0;
            for(int i = 0 ; i < 4 ; i++)
            {
                Board newBoard = new Board(n);
                newBoard = DeepCopy(board);
                newBoard.MoveUp();
                maxBlock = Math.Max(maxBlock, FindMaxValue(newBoard, moveCount + 1));
                board.Rotate();
            }

            return maxBlock;
        }

        static Board DeepCopy(Board original)
        {
            Board copy = new Board(n);
            for(int x = 0 ; x < n ; x++)
            {
                for(int y = 0 ; y < n ; y++)
                {
                    copy.SetPointValue(x, y, original.GetPointValue(x, y));
                }
            }

            return copy;
        }
    }
}