글 읽기 - c++) dfs 조합으로 풀었는데 어느 부분이 시간초과를 유발하는지 궁금합니다.

qotmd01 1년 전 0

1 . 비어 있는 사다리를 전부 후보에 집어 넣습니다.

2. 모든 조합을 대상, 백트래킹으로 사다리를 놓아봅니다.

3. 문제의 조건을 만족시키는 경우만 답을 최솟값으로 계속 갱신해 나갑니다.

비슷한 정답코드들과도 큰 차이를 못느끼겠는데 이코드는 어디서 시간초과가 발생하는지 궁급합니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int ans = 4;
bool isit[11][31];
int n,m,h;
vector<pair<int,int>> can_go;


// 사다리 최상단의 위치에서 따라 내려가봄
int go(int start){
    int temp = start;
    int cur_h = 1;
    while (cur_h != h + 1){
        if (temp + 1 <= n && isit[temp][cur_h]){
            temp = temp + 1;

        }
        else if(temp - 1 >= 1 && isit[temp-1][cur_h]){
            temp = temp - 1;

        }
        cur_h++;
    }
    return temp;
}


void backtracing(int cnt, int target){
    if (cnt == 4) return;
    if (target == can_go.size()){
        for (int i = 1; i <= n; ++i) {
            if (go(i) != i) return;
        }

        ans = min(cnt, ans);
        return;
    }
    int cur_n = can_go[target].first;
    int cur_h = can_go[target].second;
    if (!isit[cur_n+1][cur_h]){
        isit[cur_n][cur_h] = true;
        backtracing(cnt + 1, target + 1);
        isit[cur_n][cur_h] = false;
    }
    backtracing(cnt, target + 1);
}



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int a,b;
    cin >> n >> m >> h;
    for (int i = 0; i < m; ++i) {
        cin >> a >> b;
        isit[b][a] = true;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= h; ++j) {
            if (!isit[i][j]) can_go.push_back({i,j});
        }
    }

    backtracing(0,0);

    if (ans == 4) ans = -1;
    cout << ans << "\n";

    return 0;

}

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

문제

문제

출처

ICPC

c++) dfs 조합으로 풀었는데 어느 부분이 시간초과를 유발하는지 궁금합니다.

qotmd01 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말