[BaekJoon/백준] 14500번 테트로미노

아마, 내가 풀었던 문제들 중에서 최장 시간이 걸린 문제인 것 같다.

 

질문 검색에 있는 모든 반례들은 다 해본 것 같다 정말.

 

근데 자꾸 6%에서 틀렸습니다가 떴는데, 이유는 범위 지정에서 문제였다...

( x < N 해야하는데 x <= N  해서 틀린.. )

 

 

그리고 정리하는 김에, 이전에 dfs 풀이 유형에 관해 토글 / 비토글 유형으로 정리한 적이 있는데

이번엔 토글유형에 대한 세분화 정리를 한번 해볼까 합니다.

 

먼저 토글 유형의 dfs는 이러한 것을 말한다

for() {
	VISIT[x][y] = true;
	dfs(x, y);
	VISIT[x][y] = false;
}

 

한가지 유형은,

dfs 함수 외부에서 dfs를 시작 위치를 먼저 VISIT 처리 해주고 dfs를 시작하는 경우 (이번문제같은 문제)

=> 처음 뽑는 것이 메인에서 뽑는 경우. 주로 시작 위치 기준으로 상하좌우 이동 처리 관한 문제.

 

 

다른 한 가지 유형은,

처음 뽑는 것 부터 dfs 함수 내부에서 뽑는 것 ( https://hevton.tistory.com/585 )

주로 특정 범위 전체에서 몇 개를 뽑을 때.

 

 

말 그대로, 메인에서 처음 뽑는 알고리즘은 당연히 메인에서 방문처리해주고 dfs 시작해야 하는 거고

dfs에서 모두 뽑는 것은 dfs에서만 방문처리하면 되는거고 차이 뿐이다.

 

 

---

 

 

어쨌든 이번 문제 코드는 이렇다.

 

문제에서 제시된 모든 테트로미노는 DFS로 뽑을 수 있는데, 뻐큐 모양.. 은 뽑을 수 없기에

따로 함수를 만들어서 체크해준다.

/*

 ㅏ ㅓ ㅗ ㅜ 는 DFS로 못한다. 따라서 이것만 따로.
 */

#include <iostream>
#include <vector>
#define MAX(a, b) ((a>=b)?a:b)

using namespace std;

int N, M;

int MAP[500][500];
bool VISIT[500][500];

int mx[4] = {0, 0, -1, 1};
int my[4] = {1, -1, 0, 0};

int TOTAL_MAX;

void dfs(int x, int y, int cnt, int val) {
    
        
    if(cnt == 4) {
        
        if(val > TOTAL_MAX)
            TOTAL_MAX = val;
        
        return;
    }
    
    
    for(int i = 0; i < 4; i++) {
        
        
        int tx = x + mx[i];
        int ty = y + my[i];
        
        
        if(tx < 0 || tx >= N || ty < 0 || ty >= M)
            continue;
        
        
        if(!VISIT[tx][ty]) {
            
            VISIT[tx][ty] = true;
            
            dfs(tx, ty, cnt + 1, val + MAP[tx][ty]);
            
            VISIT[tx][ty] = false;
            
        }
    }
    
}


void FU(int x, int y) {
    
    int val;
    
    
    if(y - 1 >= 0 && x - 1 >= 0 && x + 1 < N) {// ㅓ
        val = MAP[x][y] + MAP[x][y - 1] + MAP[x - 1][y] + MAP[x + 1][y];
        TOTAL_MAX = MAX(TOTAL_MAX, val);
    }
        
    if(x - 1 >= 0 && x + 1 < N && y + 1 < M) {// ㅏ
        val = MAP[x][y] + MAP[x - 1][y] + MAP[x + 1][y] + MAP[x][y + 1];
        TOTAL_MAX = MAX(TOTAL_MAX, val);
    }
    if(y - 1 >= 0 && y + 1 < M && x - 1 >= 0) {// ㅗ
        val = MAP[x][y] + MAP[x - 1][y] + MAP[x][y + 1] + MAP[x][y - 1];
        TOTAL_MAX = MAX(TOTAL_MAX, val);

    }
    if(y - 1 >= 0 && y + 1 < M && x + 1 < N) {// ㅜ
        val = MAP[x][y] + MAP[x + 1][y] + MAP[x][y + 1] + MAP[x][y - 1];
        TOTAL_MAX = MAX(TOTAL_MAX, val);

    }
    
}


int main() {
    
    cin >> N >> M;
    
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++)
            cin >> MAP[i][j];
    }
    
    
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            
            FU(i, j);

            VISIT[i][j] = true;
            dfs(i, j, 1, MAP[i][j]);
            VISIT[i][j] = false;
            
        }
    }
    
    cout << TOTAL_MAX << "\n";

}

 

 

소요 시간 : 2시간

 

 

참고

https://jaimemin.tistory.com/623

https://donggoolosori.github.io/2020/10/06/boj-14500/

 

 

---

 

다시 풀어보았다. 근데 처음엔 '시간초과'가 떴고, 내가 예전에 어떻게 풀었는지 다시 확인해보니 아주 미묘한 차이로 통과받을 수 있었다.

/*
 started at 16:44
 ended at 17:20
 */

#include <iostream>
#include <vector>

using namespace std;

int N, M;

int mx[4] = {-1, 0, 0, 1};
int my[4] = {0, 1, -1, 0};

int MAX = 0;


// 볼록할 철 모양을 상하좌우 분석
void CHUL_COMPARISON(int x, int y, vector<vector<int>>& MAP, vector<vector<bool>>& VISIT) {
    
    
    
    // left
    if(x - 1 < 0 || x + 1 >= N || y + 1 >= M) // 적용해볼 수 없을 때
        ;
    else {
        
        int V = MAP[x][y] + MAP[x - 1][y] + MAP[x + 1][y] + MAP[x][y + 1];
        
        if(MAX < V)
            MAX = V;
        
    }
    
    
    
    // right
    if(x - 1 < 0 || x + 1 >= N || y - 1 < 0) // 적용해볼 수 없을 때
        ;
    else {
        
        int V = MAP[x][y] + MAP[x - 1][y] + MAP[x + 1][y] + MAP[x][y - 1];
        
        if(MAX < V)
            MAX = V;

    }
    
    // top
    if(x - 1 < 0 || y - 1 < 0 || y + 1 >= M) // 적용해볼 수 없을 떄
        ;
    else {
        
        int V = MAP[x][y] + MAP[x - 1][y] + MAP[x][y - 1] + MAP[x][y + 1];
        
        if(MAX < V)
            MAX = V;

        
    }
    
    
    // bottom
    if(y - 1 < 0 || y + 1 >= M || x + 1 >= N) // 적용해볼 수 없을 때
        ;
    else {
        
        int V = MAP[x][y] + MAP[x + 1][y] + MAP[x][y - 1] + MAP[x][y + 1];
        
        if(MAX < V)
            MAX = V;
    }
    
    
}

//이걸 해주니 시간초과 걸린다
//void CALCULATE(vector<vector<int>>& MAP, vector<vector<bool>>& VISIT) {
//
//    int TOTAL = 0;
//
//    for(int i = 0; i < N; i++) {
//        for(int j = 0; j < M; j++) {
//
//            if(VISIT[i][j]) {
//                TOTAL += MAP[i][j];
//            }
//
//        }
//    }
//
//
//    if(MAX < TOTAL)
//        MAX = TOTAL;
//
//
//
//}

void dfs(int x, int y, vector<vector<int>>& MAP, vector<vector<bool>>& VISIT, int COUNT, int VAL) {
    
    
    if(COUNT == 4) {
        
        // 4개 다 뽑음.
        
        if(MAX < VAL)
            MAX = VAL;
        
        
        return;
    }
    
    
    for(int i = 0; i < 4; i++) {
        
        int xx = x + mx[i];
        int yy = y + my[i];
        
        if(xx < 0 || xx >= N || yy < 0 || yy >= M)
            continue;
        
        
        if(!VISIT[xx][yy]) {
            
            VISIT[xx][yy] = true;
            dfs(xx, yy, MAP, VISIT, COUNT + 1, VAL + MAP[xx][yy]);
            VISIT[xx][yy] = false;
            
        }
        
        
    }
    
    
}


int main() {
    
    // 테트로미노 '하나'를 놓을 거다
    
    // ㅗ 는 상하좌우 직접 만들어주고, 나머지는 dfs로 해주면 될듯.
    
    cin >> N >> M;
    
    vector<vector<int>> MAP(N, vector<int>(M, 0));
    
    vector<vector<bool>> VISIT(N, vector<bool>(M, 0));
    
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> MAP[i][j];
        }
    }

    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            
            if(!VISIT[i][j]) {
                
                CHUL_COMPARISON(i, j, MAP, VISIT);
                
                VISIT[i][j] = true;
                dfs(i, j, MAP, VISIT, 1, MAP[i][j]);
                VISIT[i][j] = false;
            }
            
        }
    }
    
    
    cout << MAX << "\n";
    
}

 

미묘한 차이는 바로 그거였다. 모두 뽑아준 뒤에, 다시 N x M 을 돌면서, 체크해준 부분에 대해서 다시 찾아보고 하느냐

아니면, 뽑는 동시에 값을 계산하면서 진행하느냐 차이였다.

 

주석 부분을 해제하고 방법을 조금 바꿈으로써 바로 통과받을 수 있었다.