C - [시간초과 백준 14500] 테트로미노(feat. BFS, DFS, 시뮬레이션)

 

2025.01.07 - [Computer Science/알고리즘 문제] - C - [백준 1941] 소문난 칠공주 (feat. 백트래킹, DFS)

C - [백준 1941] 소문난 칠공주 (feat. 백트래킹, DFS)

 

 

소문난 칠공주 문제와 비슷한 알고리즘 구조를 가지고 있다고 판단하여, DFS를 이용한 조합을 구한 후 BFS로 인접성 검사를 진행하여 문제를 풀었습니다. 구현에 성공하여 출력도 정상적으로 나오고 있으나, 소문난 칠공주 문제의 최대 크기는 5 * 5  해당 문제는 맵 N * M 최대 크기가 500 * 500 (4 ≤ N, M ≤ 500) 이기 때문에 같은 구조를 갖더라도 시간초과 에러가 발생하여 실패한 케이스입니다. 

 

처음 알고리즘 설계 할때 최대 크기에 대해 인지를 했으나 시간 초과를 판단하는 방법을 모르고 있었기 때문에 실패할지말지 판단이 안서 일단 알고있는대로 구현했으나 역시나 실패하였습니다.

 

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

 

/*
https://www.acmicpc.net/problem/14500
C_BOJ_14500_테트로미노

1. 조합으로 4개 뽑기 (백트래킹, DFS)
2. 4개의 연결성 확인 (BFS)
3. 연결이 되어 있다면 합 구하기
4. 합과 최대값 비교
*/

#include <stdio.h>

int N, M = 0;
int map[500][500] = {0};
int MAX = 0;

// 조합
int selected_index[4][2];

// 큐 구성품
int visited[4];
int rear = 0;
int front = 0;
int queue[4][2];

//방향 구성품
int dir_x[4] = {1,-1,0,0};
int dir_y[4] = {0,0,1,-1};

void enqueue(int x, int y){
    queue[rear][0] = x;
    queue[rear][1] = y;
    rear ++;
}

void dequeue(int* x, int* y){
    *x = queue[front][0];
    *y = queue[front][1];
    front ++;
}

void bfs(){
    for(int i = 0 ; i < 4; i ++){
        visited[i] = 0;
        
    }
    
    front = 0;
    rear = 0;
    int count = 1;
    enqueue(selected_index[0][0], selected_index[0][1]);
    visited[0] = 1;
    while(front < rear){
        int x, y = 0;
        dequeue(&x, &y);
        for(int i = 0 ; i < 4; i ++){
            int nx = x + dir_x[i];
            int ny = y + dir_y[i];
            for(int j  = 0 ; j < 4; j ++){
                if(selected_index[j][0] == nx && selected_index[j][1] == ny && visited[j] == 0){
                    count ++;
                    enqueue(nx, ny);
                    visited[j] = 1;
                }
            }
        }
    }
    if(count == 4){
        // 최대 값 비교
        int sum = 0;
        for(int i = 0 ; i < 4; i ++){
            sum += map[selected_index[i][1]][selected_index[i][0]];
        }
        if(MAX < sum){
            MAX = sum;
        }
    }
}


void combination(int depth, int index){
    if(depth == 4){
        bfs();
        return;
    }

    for(int i = index; i < N * M; i++){
        int x = i % M;
        int y = i / M;
        selected_index[depth][0] = x;
        selected_index[depth][1] = y;
        combination(depth + 1, i + 1);
        }
}

int main() {
    scanf("%d %d", &N, &M);
    for(int i = 0 ; i < N; i ++){
        for(int j = 0; j < M; j ++){
            scanf("%d", &map[i][j]);
        }
    }

    combination(0,0);
    printf("%d", MAX);
    return 0;
}