[BOJ/백준] 14500 테트로미노

● [문제번호 14500] 테트로미노

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

14500번: 테트로미노

 

● 알아야 할 것

: 브루트 포스 (Brute Force)

 

 

● 풀이 과정

: [500 - 브루트 포스] 문제집에 있는 문제

 

: 풀이 과정이나 떠올리기 어려워서 구글링을 했다.

BFS 방법 + 'ㅗ' 형태 예외 처리를 하는 코드가 꽤 있었지만,

브루트 포스에 맞게 하드코딩했다.

 

: 각 형태에 마다 나올 수 있는 모습을 고려한다. (총 19가지)

사진 참고 : https://lollolzkk.tistory.com/7

각 형태마다 범위를 벗어나는 경우가 없게 조심하며,

빠짐없이 구현한다.

 

 

● 주의 할 것

: 범위에 벗어나지 않게 조심한다.

 

: 구현하고 틀리는 경우 오류가 되는 부분은 디버깅으로 찾는다.

예를 들어

4 5

1 9 9 1 1

9 9 1 1 1

1 1 1 1 1

1 1 1 1 1

와 같이 형태를 만들어 제대로 나오는 지 확인한다.

 

 

● 참고 할 것

: 풀이과정

https://lollolzkk.tistory.com/7

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

int bf[500][500];
int N, M, sol;

// 현재 최댓값과 비교
void compare(int num)
{
    if(sol < num)
        sol = num;
}

// ㅡ 형태
void check1(int a, int b)
{
    // 가로 : 1가지
    if(b + 3 < M)
    {
        int total = 0;
        for(int i = 0; i < 4; i++)
            total += bf[a][b + i];
        compare(total);
    }
    
    // 세로 : 1가지
    if(a + 3 < N)
    {
        int total = 0;
        for(int i = 0; i < 4; i++)
            total += bf[a + i][b];
        compare(total);
    }
}

// ㅁ 형태
void check2(int a, int b)
{
    // 가로, 세로 구분 없이 1가지
    if(a + 1 < N && b + 1 < M)
    {
        int total = bf[a][b] + bf[a + 1][b] + bf[a][b + 1] + bf[a + 1][b + 1];
        compare(total);
    }
}

// ㄴ 형태
void check3(int a, int b)
{
    // 가로 : 4가지
    // 튀어나온 부분이 아래를 향하는 경우 : 2가지
    if(a + 1 < N && b + 2 < M)
    {
        int total = bf[a][b] + bf[a][b + 1] + bf[a][b + 2];
        total += bf[a + 1][b];
        compare(total);
        total += (bf[a + 1][b + 2] - bf[a + 1][b]);
        compare(total);
    }
    
    // 튀어나온 부분이 위를 향하는 경우 : 2가지
    if(a - 1 >= 0 && b + 2 < M)
    {
        int total = bf[a][b] + bf[a][b + 1] + bf[a][b + 2];
        total += bf[a - 1][b];
        compare(total);
        total += (bf[a - 1][b + 2] - bf[a - 1][b]);
        compare(total);
    }
    
    // 세로 : 4가지
    // 튀어나온 부분이 왼쪽을 향하는 경우 : 2가지
    if(b - 1 >= 0 && a + 2 < N)
    {
        int total = bf[a][b] + bf[a + 1][b] + bf[a + 2][b];
        total += bf[a][b - 1];
        compare(total);
        total += (bf[a + 2][b - 1] - bf[a][b - 1]);
        compare(total);
    }
    
    // 튀어나온 부분이 오른쪽을 향하는 경우 : 2가지
    if(b + 1 < M && a + 2 < N)
    {
        int total = bf[a][b] + bf[a + 1][b] + bf[a + 2][b];
        total += bf[a][b + 1];
        compare(total);
        total += (bf[a + 2][b + 1] - bf[a][b + 1]);
        compare(total);
    }
}

// ㄱㄴ 이어진 형태
void check4(int a, int b)
{
    // 가로 : 2가지
    if(b - 1 >= 0 && b + 1 < M && a + 1 < N)
    {
        int total = bf[a][b] + bf[a + 1][b];
        total += (bf[a][b - 1] + bf[a + 1][b + 1]);
        compare(total);
        total += (bf[a + 1][b - 1] + bf[a][b + 1] - bf[a][b - 1] - bf[a + 1][b + 1]);
        compare(total);
    }
    
    // 세로 : 2가지
    if(a - 1 >= 0 && a + 1 < N && b + 1 < M)
    {
        int total = bf[a][b] + bf[a][b + 1];
        total += (bf[a - 1][b] + bf[a + 1][b + 1]);
        compare(total);
        total += (bf[a + 1][b] + bf[a - 1][b + 1] - bf[a - 1][b] - bf[a + 1][b + 1]);
        compare(total);
    }
}

// ㅗ 형태
void check5(int a, int b)
{
    // 가로 : 2가지
    if(b + 2 < M)
    {
        int total = bf[a][b] + bf[a][b + 1] + bf[a][b + 2];
        // 튀어나온 부분이 위를 향하는 경우
        if(a - 1 >= 0)
        {
            total += bf[a - 1][b + 1];
            compare(total);
            total -= bf[a - 1][b + 1];
        }
        // 튀어나온 부분이 아래를 향하는 경우
        if(a + 1 < N)
        {
            total += bf[a + 1][b + 1];
            compare(total);
        }
    }
    
    // 세로 : 2가지
    if(a + 2 < N)
    {
        int total = bf[a][b] + bf[a + 1][b] + bf[a + 2][b];
        // 튀어나온 부분이 왼쪽을 향하는 경우
        if(b - 1 >= 0)
        {
            total += bf[a + 1][b - 1];
            compare(total);
            total -= bf[a + 1][b - 1];
        }
        // 튀어나온 부분이 오른쪽을 향하는 경우
        if(b + 1 < M)
        {
            total += bf[a + 1][b + 1];
            compare(total);
        }
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> M;
    
    for(int n = 0; n < N; n++)
        for(int m = 0; m < M; m++)
            cin >> bf[n][m];
    
    for(int n = 0; n < N; n++)
    {
        for(int m = 0; m < M; m++)
        {
            check1(n, m);
            check2(n, m);
            check3(n, m);
            check4(n, m);
            check5(n, m);
        }
    }
    
    cout << sol;

    return 0;
}

 

 

● [백준] - [알고리즘 중급 1/3] - [531 - 브루트 포스 - 재귀 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	6603	로또	https://pirateturtle.tistory.com/301
2	1182	부분수열의 합	https://pirateturtle.tistory.com/302
3	14225	부분수열의 합	https://pirateturtle.tistory.com/303
4	14888	연산자 끼워넣기	https://pirateturtle.tistory.com/304
5	15658	연산자 끼워넣기 (2)	https://pirateturtle.tistory.com/305
6	14500	테트로미노	https://pirateturtle.tistory.com/306
7	16197	두 동전	https://pirateturtle.tistory.com/307
8	16198	에너지 모으기	https://pirateturtle.tistory.com/308
9	9663	N-Queen	https://pirateturtle.tistory.com/309
10	2580	스도쿠	https://pirateturtle.tistory.com/310
11	4574	스도미노쿠	https://pirateturtle.tistory.com/311
12	1987	알파벳	https://pirateturtle.tistory.com/312