글 읽기 - 시간 복잡도 질문입니다..

adh30 4년 전 0

완전 탐색으로만 풀려고 했더니 4^400 이라는 시간 복잡도가 나와 시간 초과가 들 거 같다는 생각에,

https://lmcoa15.tistory.com/30 에 있는 코드를 참조하여 백트래킹을 이용하여 풀었습니다.

A~Z를 기록하는 배열을 두고, 해당 알파벳을 전에 방문했었다면 탐색을 그만두는 방식으로 진행됩니다.

하지만 이 경우 시간 복잡도를 구하는 법을 모르겠습니다 ㅠㅠ.. 혹시 도움을 주실 수 있으실까요?

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int R,C;
vector<vector<char> > v;
int alphabet[26] = {0}; // A ~ Z
int ans = -1;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

void dfs(int row, int col, int cnt){
    ans = max(ans, cnt);
    
    for(int i=0; i<4; i++){
        int nx = row + dx[i];
        int ny = col + dy[i];
        if(nx < 0 || nx >= R || ny < 0 || ny >= C)  continue;
        
        int nextChar = (int)v[nx][ny] - 65;
        if(alphabet[nextChar] == 0){ // 이전에 거쳐오지 않은 알파벳이라면
            alphabet[nextChar] = 1;
            dfs(nx,ny,cnt+1);
            alphabet[nextChar] = 0;
        }
    }
}
int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin>>R>>C;
    v.assign(R, vector<char>(C,'0'));
    
    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
            cin>>v[i][j];
        }
    }
    
    alphabet[(int)v[0][0]-65] = 1;
    dfs(0,0,1);
    
    cout<<ans;
    
    return 0;
}

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

문제

문제

출처

ICPC

시간 복잡도 질문입니다..

adh30 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말