글 읽기 - 시간초과 질문입니다.

yonghole 3년 전 0

해당 코드는 우선, 0~24까지의 숫자 중에 7개를 뽑는 조합을 백트랙킹으로 모두 구하도록 하였습니다.

7번째 숫자를 뽑은 후 백트랙킹의 기저 조건이 되면, S가 4 개 이상인지와 해당 숫자들이 좌표상에서 모두 연결되어 있는지를 bfs로 확인하게 하였습니다.

문제는, 시간 초과가 나옵니다.

중간 중간 로그를 찍어봤을 때 제가 의도한대로 증가하고 있다는 건 알겠는데, 너무 오래 걸립니다.

다만 여기서 어떤 부분을 수정하여 시간 초과가 나지 않게 만들 수 있는지 생각이 나지 않아 질문드립니다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;
char arr[25];
bool isused[25];
int num[7];
int y_iter[4] = {1,0,-1,0};
int x_iter[4] = {0,1,0,-1};
int cnt=0;
int s_count = 0;

bool checkAdjacent(){
    queue<pair<int, int> > q;
    int y = num[0] / 5;
    int x = num[0] % 5;
    int adj_count = 0;
    bool checked[25] = {false,};

    q.push(make_pair(y,x));
    checked[num[0]] = true;
    adj_count ++;

    while(!q.empty()){
        pair<int, int> cur = q.front();
        q.pop();
    
        for(int i=0;i<4;i++){
            int y = cur.first + y_iter[i];
            int x = cur.second + x_iter[i];

            if(y >=0 && x>=0 && y<5 && x < 5){
                int tmp = y * 5 + x;
                if(isused[tmp] && !checked[tmp]){
                    q.push(make_pair(y,x));
                    checked[tmp] = true;
                    adj_count ++;
                    if(adj_count==7){
                    return true;
                    }
                }
            }
        } 
    }
    return false;

}

void btk(int n){
    if(n==7){
        // check if s more than 4
        // check adjacency
        if(checkAdjacent() && s_count >=4){
            cnt++;
        }
        return;
    }
    for(int i=0;i<25;i++){
        if(!isused[i]){
            num[n] = i;
            if(arr[i]=='S'){
                s_count++;
            }
            isused[i] = true;
            btk(n+1);
            isused[i] = false;
            if(arr[i]=='S'){
                s_count--;
            }
        }
    }    
}

int main(){
    for(int i=0;i<5;i++){
        string a;
        cin >> a;
        for(int j=0;j<5;j++){
            arr[5*i+j] = a[j];
        }
    }

    btk(0);
    cout << cnt;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 질문입니다.

yonghole 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말