[C#] 퍼즐 조각 채우기

프로그래머스 문제

https://school.programmers.co.kr/learn/courses/30/lessons/84021

풀이 후기

1. 분석

문제를 보자마자 느낄 수 있었다. 그냥 BFS나 써서 게임 구현하는 문제다. 그리고 200줄은 작성해야 하겠구나... 혹시나 해서 질문하기도 살펴봤는데 그냥 하라는 얘기 밖에 없었다.

요즘 IDE의 도움을 안받고 작성하는 연습을 하고 있었는데, 자신 없어서 그냥 라이더를 켰다.

2. 실행 결과

3. 코드

using System;
using System.Collections.Generic;

public class Solution {
    public static (int, int)[] Move = { (1, 0), (-1, 0), (0, 1), (0, -1) };
    public static int BoardLen = 0;
    public static int[,] Board;
    public static int[,] Table;
    
    public Queue<Block>[] tableQueue = new Queue<Block>[7];
    public Queue<Block>[] boardQueue = new Queue<Block>[7];

    public class Block
    {
        private (int, int) realPos;
        private (int, int) centerPos;
        private int xMin = 12;
        private int yMin = 12;
        private int xMax = 0;
        private int yMax = 0;
        
        public int[,] shape = new int[11, 11];
        public int count;
        public int xLen;
        public int yLen;

        public Block(int x, int y)
        {
            count = 0;
            realPos = (x, y);
            centerPos = (5, 5);
        }
        
        public void AddShape((int, int) pos)
        {
            var tx = pos.Item1 - realPos.Item1 + centerPos.Item1;
            var ty = pos.Item2 - realPos.Item2 + centerPos.Item2;

            if (xMin > tx)
            {
                xMin = tx;
            }
            
            if (yMin > ty)
            {
                yMin = ty;
            }
            
            if (xMax < tx)
            {
                xMax = tx;
            }
            
            if (yMax < ty)
            {
                yMax = ty;
            }
            
            shape[tx, ty] = 1;
            count++;
        }

        public void TrimShape()
        {
            xLen = xMax - xMin + 1;
            yLen = yMax - yMin + 1;

            var temp = new int[xLen, yLen];

            for (int x = 0; x < xLen; x++)
            {
                for (int y = 0; y < yLen; y++)
                {
                    temp[x, y] = shape[x + xMin, y + yMin];
                }
            }

            shape = temp;
        }

        public bool IsSimilarBlock(int xLen, int yLen)
        {
            bool con1 = this.xLen == xLen || this.xLen == yLen;
            bool con2 = this.yLen == yLen || this.yLen == xLen;

            return con1 && con2;
        }
    }
    
    public bool CanMove((int, int) pos, int w, int[,] check, (int, int) dir, out (int, int) newPos)
    {
        var newX = pos.Item1 + dir.Item1;
        var newY = pos.Item2 + dir.Item2;
        
        if (newX < 0 || newY < 0 || newX >= BoardLen || newY >= BoardLen || check[newX, newY] == w || check[newX, newY] == -1)
        {
            newPos = (0, 0);
            return false;
        }

        newPos = (newX, newY);
        return true;
    }

    public void CheckFourDir((int, int) pos, int w, int[,] check, Queue<(int, int)> queue)
    {
        foreach (var dir in Move)
        {
            if (CanMove(pos, w, check, dir, out var newPos))
            {
                check[newPos.Item1, newPos.Item2] = -1;
                queue.Enqueue(newPos);
            }
        }
    }

    public void ProcessingBlocks(int x, int y, int w, int[,] map, Queue<Block>[] queues)
    {
        var nextTile = new Queue<(int, int)>();
        var block = new Block(x, y);
        nextTile.Enqueue((x, y));
        map[x, y] = -1;
        
        while (nextTile.Count > 0)
        {
            var tile = nextTile.Dequeue();
            block.AddShape(tile);
            CheckFourDir(tile, w, map, nextTile);
        }

        block.TrimShape();
        
        if (queues[block.count] == null)
        {
            queues[block.count] = new Queue<Block>();
        }

        queues[block.count].Enqueue(block);
    }

    public void ProcessingTable(int[,] data)
    {
        for (int x = 0; x < BoardLen; x++)
        {
            for (int y = 0; y < BoardLen; y++)
            {
                if (data[x, y] == 1)
                {
                    ProcessingBlocks(x, y, 0, Table, tableQueue);
                }
            }
        }
    }
    
    public void ProcessingBoard(int[,] data)
    {
        for (int x = 0; x < BoardLen; x++)
        {
            for (int y = 0; y < BoardLen; y++)
            {
                if (data[x, y] == 0)
                {
                    ProcessingBlocks(x, y, 1, Board, boardQueue);
                }
            }
        }
    }
    
    public int[,] RotateMatrix(int[,] matrix)
    {
        int rowCount = matrix.GetLength(0);
        int colCount = matrix.GetLength(1);
        int[,] rotatedMatrix = new int[colCount, rowCount];

        for (int row = 0; row < rowCount; row++)
        {
            for (int col = 0; col < colCount; col++)
            {
                rotatedMatrix[col, rowCount - row - 1] = matrix[row, col];
            }
        }

        return rotatedMatrix;
    }

    public bool IsSameArray(int[,] arr1, int[,] arr2)
    {
        var lenX = arr1.GetLength(0);
        var lenY = arr1.GetLength(1);

        if (lenX != arr2.GetLength(0) || lenY != arr2.GetLength(1))
        {
            return false;
        }

        for (int x = 0; x < lenX; x++)
        {
            for (int y = 0; y < lenY; y++)
            {
                if (arr1[x, y] != arr2[x, y])
                {
                    return false;
                }
            }
        }
        
        return true;
    }

    public bool RotateArrayCheck(int[,] arr1, int[,] arr2)
    {
        if (IsSameArray(arr1, arr2))
        {
            return true;
        }

        var newArr = arr2;
        for (int i = 0; i < 3; i++)
        {
            newArr = RotateMatrix(newArr);

            if (IsSameArray(arr1, newArr))
            {
                return true;
            }
        }

        return false;
    }

    public int solution(int[,] game_board, int[,] table)
    {
        Board = game_board;
        Table = table;
        BoardLen = game_board.GetLength(0);

        ProcessingBoard(Board);
        ProcessingTable(Table);

        var answer = 0;
        for (int i = 1; i < 7; i++)
        {
            if (boardQueue[i] == null || tableQueue[i] == null)
            {
                continue;
            }

            while (boardQueue[i].Count > 0)
            {
                var blank = boardQueue[i].Dequeue();

                var loopMax = tableQueue[i].Count;
                while (0 < loopMax)
                {
                    var tile = tableQueue[i].Dequeue();

                    if (blank.IsSimilarBlock(tile.xLen, tile.yLen))
                    {
                        if (RotateArrayCheck(blank.shape, tile.shape))
                        {
                            answer += i;
                            break;
                        }
                    }

                    tableQueue[i].Enqueue(tile);
                    loopMax--;
                }
            }
        }
        
        return answer;
    }
}

4. 코드 설명

    public class Block
    {
        private (int, int) realPos;
        private (int, int) centerPos;
        private int xMin = 12;
        private int yMin = 12;
        private int xMax = 0;
        private int yMax = 0;
        
        public int[,] shape = new int[11, 11];
        public int count;
        public int xLen;
        public int yLen;
    }

객체지향언어 답게 객체지향으로 풀려고 노력을 했다. Processing~를 통해 주어진 맵을 탐색하고, BFS로 탐색한 칸을 Block class로 가공하는 방식으로 진행한다.

Block의 길이는 최대 6칸으로 주어진다. 때문에 중앙에 1개를 제외한 최대 거리인 5만큼의 크기의 배열이 필요하다. 11*11 배열이 필요하다는 뜻.

public Block(int x, int y)
{
    count = 0;
    realPos = (x, y);
    centerPos = (5, 5);
}
        
public void AddShape((int, int) pos)
{
    var tx = pos.Item1 - realPos.Item1 + centerPos.Item1;
    var ty = pos.Item2 - realPos.Item2 + centerPos.Item2;

    if (xMin > tx)
    {
        xMin = tx;
    }
            
    if (yMin > ty)
    {
        yMin = ty;
    }
            
    if (xMax < tx)
    {
        xMax = tx;
    }
            
    if (yMax < ty)
    {
        yMax = ty;
    }
            
    shape[tx, ty] = 1;
    count++;
}

조금 고민했던 부분은 블럭을 어떻게 채울 것인가. 중앙 지점을 5로 잡아두고 [해당 블럭 지점 - 시작한 지점] 에 중앙 좌표를 계산해서 얼마나 떨어져 있는가를 판별하는 느낌으로 Block 배열을 채우게 만들었다.

public void TrimShape()
{
    xLen = xMax - xMin + 1;
    yLen = yMax - yMin + 1;

    var temp = new int[xLen, yLen];

    for (int x = 0; x < xLen; x++)
    {
        for (int y = 0; y < yLen; y++)
        {
            temp[x, y] = shape[x + xMin, y + yMin];
        }
    }

    shape = temp;
}

배열은 돌려야 하니까 좌표 최댓값과 최솟값을 참고하여 줄이는 작업도 포함. 이렇게 해두면 블럭의 가로 세로 값을 기반으로 복잡도를 쪼금 줄일 수 있다.

var answer = 0;
for (int i = 1; i < 7; i++)
{
    if (boardQueue[i] == null || tableQueue[i] == null)
    {
        continue;
    }

    while (boardQueue[i].Count > 0)
    {
        var blank = boardQueue[i].Dequeue();

        var loopMax = tableQueue[i].Count;
        while (0 < loopMax)
        {
            var tile = tableQueue[i].Dequeue();

            if (blank.IsSimilarBlock(tile.xLen, tile.yLen))
            {
                if (RotateArrayCheck(blank.shape, tile.shape))
                {
                    answer += i;
                    break;
                }
            }

            tableQueue[i].Enqueue(tile);
            loopMax--;
        }
    }
}
        
return answer;

block을 다 만들었으면 비교만 하면 끝. 이전에 만들어둔 block은 칸 갯수에 따라 큐 배열에 저장했다. 이렇게 하면 칸수가 다른 block은 비교하지 않아서 편함. 그 다음은 평범하게 1개 꺼내서 가로 세로가 비슷한지 확인하고, 돌려서 비교해보고, 정답 추가하고... block으로 가공하는게 대부분이고 굳이 어려운건 배열 돌리기인데 그냥 따라서 쳤다.

여담으로 이 문제 정답률이 14%던데 다른 사람들은 코드가 너무 길어져서 그냥 포기한게 아닐까 생각해본다.