11559. 뿌요뿌요 (C#)

문제

• 뿌요뿌요 | 골드IV (2025년 9월 2일 기준)
• 알고리즘 분류
  • 구현
  • 그래프 이론
  • 그래프 탐색
  • 시뮬레이션
  • 너비 우선 탐색

접근

뿌요뿌요의 규칙

상하좌우로 4개 이상 같은 색상으로 연결된 뿌요가 있다면 연결된 뿌요가 한번에 삭제된다. 뿌요가 삭제되면 위에 있던 뿌요들은 중력의 영향을 받아 떨어지게 된다. 떨어지고 난 뒤 다시 같은 색의 뿌요가 4개 이상 연결된 경우 뿌요가 터지게 되는데, 뿌요들이 내려와서 다시 터짐을 반복할 때 마다 1연쇄씩 늘어난다.

• 연결된 뿌요 찾기
  
  • BFS로 탐색할 수 있을 것 같다.
• 4개 이상 연결된 경우에만 뿌요를 삭제
  • BFS로 탐색하면서 좌표를 저장해 두었다가 4개 이상 연결된 경우에만 해당 좌표에 있는 뿌요를 삭제하자
• 뿌요에 중력 적용
  • 뿌요 사이의 빈공간이 없이 바닥부터 쌓여 있도록 해야 한다
• 4개 이상 연결된 뿌요가 없을 때 까지 반복
  • 뿌요 그룹 삭제(연쇄+1) -> 중력적용 -> 그룹삭제(연쇄+1) -> 중력 적용 -> ... (반복)
• 연쇄 카운트 출력

풀이

Main() : 뿌요뿌요 필드를 입력받고 결과를 출력한다

static void Main(string[] args)
{
    /* 입력
     * 12개의 줄에 필드의 정보가 주어짐
     * 각 줄에는 6개의 문자가 있다
     * . 은 빈공간
     * . 이 아닌 것은 각각의 색깔의 뿌요(R,G,B,P,Y)
     * 뿌요 아래에 빈 칸이 있는 경우는 없다
     */

    char[,] map = new char[12, 6];
    for (int i = 0; i < 12; i++)
    {
        string input = Console.ReadLine();

        int colIndex = 0;
        foreach (char item in input.ToCharArray())
        {
            map[i, colIndex] = item;
            colIndex++;
        }


    }
    Console.WriteLine(calcChain(map));
}

calcChain(char[,]) :  뿌요뿌요 맵을 받아서 연쇄를 계산하여 반환한다

static int calcChain(char[,] map)
{
    int result = 0;
    /*1. 상하좌우로 연결된 뿌요 확인 및 삭제
     * -> 4개 이상 연결된 뿌요가 있으면 삭제, result++
     *2. 각 뿌요에 중력 적용 -> 공중에 떠있는 뿌요가 없을 때 까지
     *3. 4개 이상 연결된 뿌요가 없을때 까지 반복
     */
    while (removeGroup(map))
    {
        result++;
        applyGravity(map);
    }
    return result;
}

removeGroup(char[,]) 4개 이상 인접한 뿌요를 BFS로 탐색하고 제거한다. 제거한 뿌요가 있는 경우 true를 반환한다

static bool removeGroup(char[,] map)
{
    bool result = false;
    bool[,] visited = new bool[12, 6];

    //4개 이상 그룹된 뿌요가 있는지 확인 및 그룹 삭제
    //BFS로 탐색
    for (int i = 0; i < 12; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            if (map[i, j] == '.' || visited[i, j]) continue;

            int count = 0;
            char color = map[i, j]; //시작 지점 색상

            //BFS
            Queue<Point> queue = new Queue<Point>();
            Stack<Point> stack = new Stack<Point>();

            queue.Enqueue(new Point(i, j));
            visited[i, j] = true;
            stack.Push(new Point(i, j));
            while (queue.Any())
            {
                Point curr = queue.Dequeue();

                count++;

                Point[] cardinates = new Point[4]
                {
                    new Point(curr.row + 1, curr.col),
                    new Point(curr.row - 1, curr.col),
                    new Point(curr.row, curr.col + 1),
                    new Point(curr.row, curr.col - 1)
                };
                foreach (Point p in cardinates)
                {
                    if (p.row >= 0 && p.col >= 0 && p.row < 12 && p.col < 6 && !visited[p.row, p.col] && map[p.row, p.col] == color) //유효한 좌표 & 방문하지 않은 좌표 & 같은 색상의 좌표
                    {
                        queue.Enqueue(p);
                        visited[p.row,p.col] = true;
                        stack.Push(p);
                    }
                }

            }
            //4개 이상 그룹이면 그룹 삭제
            if (count >= 4)
            {
                result = true; //삭제한 그룹이 있으면 true
                foreach (Point p in stack)
                {
                    //그룹의 뿌요 삭제
                    map[p.row, p.col] = '.';
                }
            }
        }
    }

    return result; //삭제한 그룹이 있으면 true
}

applyGravity() : 뿌요에 중력 적용 (빈 공간 제거)

static void applyGravity(char[,] map)
{
    //뿌요에 중력을 적용
    //각 열의 모든 색상을 스택에 쌓고
    //열을 날린 다음 맨 아래부터 재배치
    Stack<char> stack = new Stack<char>();
    for (int col = 0; col < 6; col++)
    {
        for (int row = 0; row < 12; row++)
        {
            if (map[row, col] != '.')
            {
                stack.Push(map[row, col]);
                map[row, col] = '.';
            }
        }

        //맨 아래부터 재배치
        int rowIndex = 11;
        while (stack.Count > 0)
        {
            char puyo = stack.Pop(); // 스택에서 요소를 꺼냄
            map[rowIndex, col] = puyo;
            rowIndex--;
        }
    }
}