테트로미노

코드

[ 시간초과 풀이 ] - next_permutation

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#define ll long long
#define ull unsigned long long
using namespace std;
// 11:11 ~
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int N,M,ans;
int board[505][505];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            cin >> board[i][j];
    int ch[N*M];
    fill(ch, ch+N*M, 1);
    for(int i=0;i<4;i++)
        ch[i] = 0;
    do{
        bool tmp[N][M];
        bool vis[N][M];
        int sum=0;
        pair<int,int> start = {-1,-1};
        for(int i=0;i<N;i++)
        {
            fill(tmp[i], tmp[i]+M, false);
            fill(vis[i], vis[i]+M, false);
        }
        for(int i=0;i<N*M;i++)
            if(ch[i] == 0){
                int ny = i/M; // 가로 크기의 몫
                int nx = i%M; // 가로 크기의 나머지
                tmp[ny][nx] = true;
                sum += board[ny][nx];
                if(start.first == -1)
                    start = {ny,nx};
            }
        /* BFS로 인접한 4점인지 확인 */
        queue<pair<int,int>> q;
        q.push(start);
        vis[start.first][start.second] = true;
        int cnt=1;
        while(!q.empty())
        {
            auto cur = q.front(); q.pop();
            for(int dir=0;dir<4;dir++)
            {
                int ny = cur.first + dy[dir];
                int nx = cur.second + dx[dir];
                if(nx<0 or ny<0 or nx>=M or ny>=N) continue;
                if(vis[ny][nx] or tmp[ny][nx] == false) continue;
                cnt++;
                vis[ny][nx] = true;
                q.push({ny,nx});
            }
        }
        /* 인접한 점의 개수가 4개 이하이면 pass */
        if(cnt < 4) continue;
        /* 인접합 점 4개의 점수 합 계산 */
        ans = max(ans, sum);
    }while(next_permutation(ch, ch+(N*M)));
    cout << ans;
    return 0;
}

• 로직
  • N*M개의 점들 중 인접한 4개의 점 을 골라서 합을 구하는 방식으로 최대값을 구함
    (next_permutation을 이용한 조합으로 경우의 수를 구하기)
• 결과
  : 시간초과
  • next_permutation() --> O(N*M)
  • next_permutation() 내부 에 있는 vis, tmp 초기화 --> O(N*M)
  • 총 O((N*M)^2) = O(250000*250000) = 약 O(10^10)

• 깨달은 것
  • next_permutation으로 조합을 구할 때 ch를 1로 초기화 한 후 뽑을 개수만큼 0으로 초기화 해야함
    (반대로 0으로 초기화하고 1로 넣으면 올바르게 실행되지 X)

[ 정답 풀이 ]

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#define ll long long
#define ull unsigned long long
using namespace std;
// 11:11 ~ 12:49
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int N,M,ans;
int board[505][505];
bool vis[505][505];
vector<int> arr(4);
void DFS(int y, int x, int depth)
{   
    if(depth == 4){
        int sum=0;
        for(auto a : arr)
            sum += a;
        ans = max(ans, sum);
        return;
    }
    for(int dir=0;dir<4;dir++)
    {
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        if(nx<0 or ny<0 or nx>=M or ny>=N) continue;
        if(vis[ny][nx]) continue;
        vis[ny][nx] = true;
        arr[depth] = board[ny][nx];
        DFS(ny, nx, depth+1);
        vis[ny][nx] = false;
    }
}
bool check(int y, int x){
    if(y<0 or x<0 or y>=N or x>=M) return false;
    return true;
}
void good(int y, int x){

    int result=0;
    /* ㅗ 검사 */
    if(check(y,x) and check(y+1,x) and check(y+1,x-1) and check(y+1,x+1)){
        int sum=  board[y][x] + board[y+1][x] + board[y+1][x-1] + board[y+1][x+1];
        result = max(sum, result);
    }

    /* ㅏ 검사 */
    if(check(y,x) and check(y,x-1) and check(y-1,x-1) and check(y+1,x-1)){
        int sum = board[y][x] + board[y][x-1] + board[y-1][x-1] + board[y+1][x-1];
        result = max(sum, result);
    }

    /* ㅜ 검사 */
    if(check(y,x) and check(y-1,x) and check(y-1,x-1) and check(y-1,x+1)){
        int sum = board[y][x] + board[y-1][x] + board[y-1][x-1] + board[y-1][x+1];
        result = max(sum, result);
    }

    /* ㅓ 검사 */
    if(check(y,x) and check(y,x+1) and check(y-1,x+1) and check(y+1,x+1)){
        int sum = board[y][x] + board[y][x+1] + board[y-1][x+1] + board[y+1][x+1];
        result = max(sum, result);
    }
    ans = max(result, ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            cin >> board[i][j];

    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
        {
            /* ㅗ 모양을 제외한 나머지 4유형은 4-depth의 DFS로 해결 가능 */
            vis[i][j] = true;
            DFS(i,j,0);
            vis[i][j] = false;
            /* ㅗ 모양의 4가지 경우에 대해 검사 */
            good(i,j);
        }
    cout << ans;
    return 0;
}

• 핵심 아이디어
  • 'ㅗ' 모양의 블럭을 제외한 나머지 블럭은 모두 4-depth의 DFS로 탐색 할 수 있다
  • DFS + 모든 점에 대해 'ㅗ'블럭의 경우의수 4가지 에 대한 합을 구해 최대값을 산출

• 시간복잡도
  • DFS() --> O(19) : 한 점에 대해 4-depth가 나오는 경우는 19가지
  • good() --> O(1)
  • 총 = O(N*M) = O(250000) = O(10^5)
    : 모든 점에 대해서 DFS()와 good() 수행