[C#] 테트로미노

백준 문제

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

풀이 후기

1. 분석

블록을 모두 놔둬서 최대 숫자를 찾는 문제인 줄 알았으나, 정신 차리고 보니 가장 큰 합이 나오는 블록을 찾는 문제였다. 골드 4 문제가 그렇게 어려울 리가 없긴 하다.

블록의 개수는 5개이지만 회전, 대칭까지 허용이니 실제로 계산해보면...

// I
blocks.Add(new[,]{{1, 1, 1, 1}});
blocks.Add(new[,]{{1},{1},{1},{1}});

// O
blocks.Add(new[,]{{1, 1},{1, 1}});

// L 
blocks.Add(new[,]{{1, 0},{1, 0},{1, 1}});
blocks.Add(new[,]{{0, 0, 1},{1, 1, 1}});
blocks.Add(new[,]{{1, 1, 1},{1, 0, 0}});
blocks.Add(new[,]{{1, 1},{0, 1},{0, 1}});

// J 
blocks.Add(new[,]{{0, 1},{0, 1},{1, 1}});
blocks.Add(new[,]{{1, 0, 0},{1, 1, 1}});
blocks.Add(new[,]{{1, 1, 1},{0, 0, 1}});
blocks.Add(new[,]{{1, 1},{1, 0},{1, 0}});

// S
blocks.Add(new[,]{{1, 0},{1, 1},{0, 1}});
blocks.Add(new[,]{{0, 1, 1},{1, 1, 0}});

// Z
blocks.Add(new[,]{{0, 1},{1, 1},{1, 0}});
blocks.Add(new[,]{{1, 1, 0},{0, 1, 1}});

// T
blocks.Add(new[,]{{1, 1, 1},{0, 1, 0}});
blocks.Add(new[,]{{0, 1, 0},{1, 1, 1}});
blocks.Add(new[,]{{1, 0},{1, 1},{1, 0}});
blocks.Add(new[,]{{0, 1},{1, 1},{0, 1}});

이렇게 19개가 나온다. 19개 블록이 대충 크기가 6개니까 계산하면 114번의 연산이 진행된다.

맵은 최대 500*500=250,000칸. 25만 칸에 모든 블록을 놓는다면

250,000 * 114 = 28,500,000

제한시간이 2초 = 대충 2억 번의 연산이 제한이므로 시간내에 충분히 가능하므로 BF로 열심히 구현해서 돌리면 풀 수 있다.

그냥 블록을 놓는 작업이 전부라 어려운 건 없었는데, 저번 코테에서 이거랑 비슷한 문제를 디버깅하다가 시간 다 날려서... 에휴....

2. 실행 결과

3. 코드

using System;
using System.Collections.Generic;
using System.Linq;

class Baekjoon
{
    public List<int[,]> blocks = new List<int[,]>();
    public int xLen = 0;
    public int yLen = 0;
    
    public int PutBlockInMap(int x, int y, int[,] map, int index)
    {
        var block = blocks[index];
        var blockX = block.GetLength(0);
        var blockY = block.GetLength(1);

        if (x + blockX > xLen || y + blockY > yLen) return 0;

        var sum = 0;
        for (var bx = 0; bx < blockX; bx++)
        {
            for (var by = 0; by < blockY; by++)
            {
                if (block[bx, by] == 0)
                {
                    continue;
                }

                sum += map[x + bx, y + by];
            }
        }

        return sum;
    }
    
    public void Solution(int xl, int yl, int[,] map)
    {
        xLen = xl;
        yLen = yl;
        
        // I
        blocks.Add(new[,]{{1, 1, 1, 1}});
        blocks.Add(new[,]{{1},{1},{1},{1}});
        
        // O
        blocks.Add(new[,]{{1, 1},{1, 1}});
        
        // L 
        blocks.Add(new[,]{{1, 0},{1, 0},{1, 1}});
        blocks.Add(new[,]{{0, 0, 1},{1, 1, 1}});
        blocks.Add(new[,]{{1, 1, 1},{1, 0, 0}});
        blocks.Add(new[,]{{1, 1},{0, 1},{0, 1}});
        
        // J 
        blocks.Add(new[,]{{0, 1},{0, 1},{1, 1}});
        blocks.Add(new[,]{{1, 0, 0},{1, 1, 1}});
        blocks.Add(new[,]{{1, 1, 1},{0, 0, 1}});
        blocks.Add(new[,]{{1, 1},{1, 0},{1, 0}});
        
        // S
        blocks.Add(new[,]{{1, 0},{1, 1},{0, 1}});
        blocks.Add(new[,]{{0, 1, 1},{1, 1, 0}});
        
        // Z
        blocks.Add(new[,]{{0, 1},{1, 1},{1, 0}});
        blocks.Add(new[,]{{1, 1, 0},{0, 1, 1}});
        
        // T
        blocks.Add(new[,]{{1, 1, 1},{0, 1, 0}});
        blocks.Add(new[,]{{0, 1, 0},{1, 1, 1}});
        blocks.Add(new[,]{{1, 0},{1, 1},{1, 0}});
        blocks.Add(new[,]{{0, 1},{1, 1},{0, 1}});

        var max = -1;
        for (var x = 0; x < xLen; x++)
        {
            for (var y = 0; y < yLen; y++)
            {
                var calc = Enumerable.Range(0, blocks.Count).Select(i => PutBlockInMap(x, y, map, i)).Max();
                max = Math.Max(max, calc);
            }
        }
        
        Console.WriteLine(max);
    }

    static void Main(string[] args)
    {
        var read = Console.ReadLine()!.Split(" ").Select(int.Parse).ToArray();
        var map = new int[read[0], read[1]];
        for (var i = 0; i < read[0]; i++)
        {
            var lines = Console.ReadLine()!.Split(" ");
            for (var j = 0; j < read[1]; j++)
            {
                map[i, j] = int.Parse(lines[j]);
            }
        }
        
        new Baekjoon().Solution(read[0], read[1], map);
    }
}