[백준 14500] 테트로미노

안녕하세요 !!! 우디🙇입니다.

오늘은 BFS로 푼 테트로미노 문제에 대해 설명해드릴께요.

 

문제

[백준 14500] 테트로미노

 

문제 설명

1. 테트로미노 모든 모양(좌우대칭)을 종이에 하나 하나 적재해서 최댓값 구하기.

처음에 생각해낸 방법이 노가다 방법이었습니다. (직접 해보진 않았지만 ,,,)

시간 복잡도 빅오로 계산해보았을 때

 500 X 500 X (8 X 5) = 10,000,000 (천만)

500 X 500 개의 정사각형마다 테트로미노를 놓아야 되고 테트로미노 5종류 중에 좌우대칭한 모양이 각 종류마다 대충 최대 8개 있다고 하면 저렇게 계산이 되쥬 ?

이 문제의 시간 제한이 2초 (1초를 대충 1억번의 연산으로 생각) 이니깐 시간제한에도 안걸릴 것 같고 엄청난 정성이 있다면 이 방법도 괜찮은 것 같습니다 !

🙈 : 그치만 저는 깐지나게 풀래요 ❗❗

 

2. 테트로미노 모양을 만들어가면서 최댓값 구하기.

우선, (0,0) 을 기준으로 테트로미노를 만들어가는 과정을 설명하겠습니다.

xxxxxxxxxx
1. 현재 좌표 (0,0)에서 상 , 하 , 좌 , 우로 갈 수 있는지 판단합니다.
​
2.우로 갈 수 있으므로 좌 방향을 제외한 상, 하 , 우,로 이동할 수 있는지 봅니다.
​
(이때, bfs 함수 돌고 각 방향이 어디 방향으로 갈 수 있는지는 2차원 배열 형태의 지침표를 만들었습니다.
​
                   상 | 상 좌 우
​
                   하 | 하 좌 우
​
                   좌 | 좌 상 하
​
                   우 | 우 상 하      <--- 요런식으로        )
​
3.상으로 이동하면 배열을 벗어나므로 제외. 따라서, 하(1,1) 우(0,2) 로 이동합니다.
​
4.(1) 하(1,1)에서 상 방향을 제외한 하 , 좌 , 우로 이동할 수 있는지 봅니다.
​
      하 (2,1) 좌(1,0) 우(1,2) 로 이동합니다.
​
  (2) 우(0,2)에서 좌 방향을 제외한 상 , 하 , 우로 이동할 수 있는지 봅니다.
​
      상으로 이동하면 배열을 벗어나므로 제외. 따라서, 하(1,2) 우(0,3)로 이동합니다.
​

 

이 과정을 트리 🌳로 나타내보면,

 

휴도 코드

x
//queue<pair<int, int>>cur; 현재좌표 쌍을 담는 큐
//queue<int>dir;            방향 큐
//queue<int>maxx;           최댓값 저장해 놓는 큐
​
// main문에서 현재좌표를 기준으로 상,하,좌,우 한번 움직인 상태로 bfs 돔
void bfs()
{
    for (int a = 0; a < 4; a++)// main문에서 현재좌표를 기준으로 상,하,좌,우 한번 움직인 상태로 bfs 돔. 따라서 위의 트리를 보자면 맨 위의 (우) 상태로 한번 , 만약 맨 위의 (우)가 최대(우,상,하)로 다 갈 수가 있다면 이 for문을 3번더 돌아야 하기 때문에 최대 4번 돈다.
    {
        int x = cur.front().first;
        int y = cur.front().second;
        int di = dir.front();
        int ma = maxx.front();//cur , dir , maxx 큐에 담긴 값들을 뽑아줌
​
        for (int b = 0; b < 3; b++)//각 방향에서 움직일 수 방향은 최대 3가지
        {
            if (다음으로 움직일 좌표가 배열 범위를 벗어나지 않는 범위에서 !)
            {
                cur.push(make_pair(x + dx[rf[di][b]], y + dy[rf[di][b]]));
                dir.push(rf[di][b]);
                maxx.push(ma + arr[x + dx[rf[di][b]]][y + dy[rf[di][b]]]);
                //cur , dir , maxx 에 다음 좌표와 방향 최댓값을 계산해 넣어줌
            }
        }
​
        cur.pop();
        dir.pop();
        maxx.pop();
​
        if (a == 0)
        {
            a += (3 - dir.size());
            //트리에서의 맨 처음 (우) 다음으로 넣어준 큐의 사이즈만큼 바깥 for문은 더 돌면 되므로 a               크기를 조절해준다.
        }
    }
}

 

이렇게 놓고 보니 ,,, 테트로미노 모양 하나가 빠졌죠 ❔❔

바로 법규 모양이 빠졌는데 이 모양은 위처럼 구해질 수 없으므로 따로 구해야 합니다 !

• 연속으로 같은 방향 (상상상 하하하 좌좌좌 우우우)으로 움직였을 때, 중간의 현재좌표에서 양옆 또는 위아래로 값을 더해주면 법규 모양이 되면서 최댓값을 구할 수 있습니다 ~

 

휴도코드

xxxxxxxxxx
//queue<int>fuck_max;//법규 모양 최댓값들 담아주는 큐
​
void bfs()
{
    for (int a = 0; a < 4; a++)// main문에서 현재좌표를 기준으로 상,하,좌,우 한번 움직인 상태로 bfs 돔. 따라서 위의 트리를 보자면 맨 위의 (우) 상태로 한번 , 만약 맨 위의 (우)가 최대(우,상,하)로 다 갈 수가 있다면 이 for문을 3번더 돌아야 하기 때문에 최대 4번 돈다.
    {
        int x = cur.front().first;
        int y = cur.front().second;
        int di = dir.front();
        int ma = maxx.front();//cur , dir , maxx 큐에 담긴 값들을 뽑아줌
​
        for (int b = 0; b < 3; b++)//각 방향에서 움직일 수 방향은 최대 3가지
        {
            if (다음으로 움직일 좌표가 배열 범위를 벗어나지 않는 범위에서 !)
            {
                cur.push(make_pair(x + dx[rf[di][b]], y + dy[rf[di][b]]));
                dir.push(rf[di][b]);
                maxx.push(ma + arr[x + dx[rf[di][b]]][y + dy[rf[di][b]]]);
                //cur , dir , maxx 에 다음 좌표와 방향 최댓값을 계산해 넣어줌
            }
        }
​
        cur.pop();
        dir.pop();
        maxx.pop();
​
        if (a == 0)//바깥 for문이 한번 돌면 총 3번을 움직여 3개까지의 모양이 완성됨
        {
            if (방향 큐의 맨 앞이 처음 방향과 같음)//일직선으로 만들어졌음
            {
                if (dir.front() == 0 || dir.front() == 1)//상,하 로 일직선이라면
                {
                    if(범위를 넘지 않는 선에서) 양 옆 좌표 더해줘서 fuck_max에 적재.
                }
                else if (dir.front() == 2 || dir.front() == 3)//좌,우 로 일직선이라면
                {
                    if(범위를 넘지 않는 선에서) 상 하 좌표 더해줘서 fuck_max에 적재.
                }
            }
            a += (3 - dir.size());
        }
    }
}

 

구현

xxxxxxxxxx
#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
​
void bfs();
​
int n, m;
int arr[502][502];
int answer = 0;//정답
queue<pair<int, int>>cur; //현재좌표 큐
queue<int>dir;            //방향 큐
queue<int>maxx;           //최댓값 큐
queue<int>fuck_max;       //법규 모양 따로 
​
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
​
int rf[4][4] = { {0,2,3},{1,2,3},{2,0,1},{3,0,1} };// 지침표 상(0) 하(1) 좌(2) 우(3)
​
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> arr[i][j];
​
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            for (int k = 0; k < 4; k++)
            {
                if (i + dx[k] == -1 || i + dx[k] == n || j + dy[k] == -1 || j + dy[k] == m)
                    continue;//상 하 좌 우로 움직였을 때 배열 밖을 넘어가면 다른 방향으로 이동함.
                else
                {
                    cur.push(make_pair(i + dx[k], j + dy[k]));
                    dir.push(k);
                    maxx.push(arr[i][j] + arr[i + dx[k]][j + dy[k]]);//배열 넘지 않으면 한번 이동한 상태로 큐에 넣어줌.
                    bfs();//bfs 시작
                }
                while (!maxx.empty())
                {
                    if (answer < maxx.front()) answer = maxx.front();
                    maxx.pop();
                    cur.pop();
                    dir.pop();
                }//한 좌표에서의 테트로미노 모양을 적재시켰으니 최댓값 갱신해주고 큐 비워줌.
                while (!fuck_max.empty())
                {
                    if (answer < fuck_max.front()) answer = fuck_max.front();
                    fuck_max.pop();
                }//법규 모양 큐도 최댓값 갱신해주고 큐 비워줌.
​
            }
        }
    }
    cout << answer << endl;//정답 출력
}
​
void bfs()
{
    for (int a = 0; a < 4; a++)
    {
        int x = cur.front().first;
        int y = cur.front().second;
        int di = dir.front();
        int ma = maxx.front();
​
        for (int b = 0; b < 3; b++)
        {
            if (x + dx[rf[di][b]] != -1 && x + dx[rf[di][b]] != n 
                && y + dy[rf[di][b]] != -1 && y + dy[rf[di][b]] != m)
            {
                cur.push(make_pair(x + dx[rf[di][b]], y + dy[rf[di][b]]));
                dir.push(rf[di][b]);
                maxx.push(ma + arr[x + dx[rf[di][b]]][y + dy[rf[di][b]]]);
            }
        }
​
        cur.pop();
        dir.pop();
        maxx.pop();
​
        if (a == 0)
        {
            if (dir.front() == di)//맨 처음 방향(트리의 젤 윗부분)과 같아야 일직선임.
            {
                if (dir.front() == 0 || dir.front() == 1)
                {
                    if (y - 1 != -1) fuck_max.push(maxx.front() + arr[x][y - 1]);
                    if (y + 1 != m) fuck_max.push(maxx.front() + arr[x][y + 1]);
                    //둘 다 if 문 걸어줘야 둘 다 걸림. 저는 하나 습관적으로 else if 했다가 삽질                        했어요 ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
                }
                else if (dir.front() == 2 || dir.front() == 3)
                {
                    if (x - 1 != -1) fuck_max.push(maxx.front() + arr[x - 1][y]);
                    if (x + 1 != n) fuck_max.push(maxx.front() + arr[x + 1][y]);
                }
            }
            a += (3 - dir.size());
        }
    }
}