[백준] 1987 알파벳

정말 순수하게 알파벳이 지나온 길을 저장한 뒤에 한번 재귀가 돌때마다 반복문을 돌며 저장된 알파벳을 탐색하는 방식으로 풀었다.

그런데 바로 시간초과 ㅜㅜ

 

□ 해결은 됐지만 시간초과가 된 코드

#include <bits/stdc++.h>

using namespace std;

int R1987, C1987;
vector<vector<char>> input1987(21,vector<char>(21,NULL));
vector<vector<bool>> check1987(21,vector<bool>(21,false));
vector<char> doneAlpha1987;
int result1987 = 0;

bool checkAlphabet1987(char now, int count){
    for(int i=0;i<count;++i){
        if(now == doneAlpha1987[i])
            return false;
    }
    return true;
}

void backback1987(int x, int y, int count){
    int dx[] = {0,0,1,-1};
    int dy[] = {1,-1,0,0};

    if(x<1 or x>R1987 or y<1 or y>C1987)
        return;

    for(int i=0;i<4;++i){
        int mx = dx[i] + x;
        int my = dy[i] + y;

        if(mx<1 or mx>R1987 or my<1 or my>C1987)
            continue;

        if(checkAlphabet1987(input1987[x][y], count-1) and !check1987[x][y]){

            check1987[x][y] = true;
            doneAlpha1987.push_back(input1987[x][y]);

            result1987 = max(result1987,count);
            backback1987(mx, my, count+1);

            doneAlpha1987.pop_back();
            check1987[x][y] = false;
        }
    }
}

void alphabet1987(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>R1987>>C1987;
    
    for(int i=1;i<=R1987; ++i){
        for(int j=1; j<=C1987; ++j){
            char a; cin>>a;
            input1987[i][j] = a;
        }
    }
   
    backback1987(1, 1, 1);
    cout<<result1987<<"\n";
}

 

재귀를 돌때마다 반복문을 돌면서 확인하는 방식이 비효율적이고 시간초과가 발생하므로

알파벳 순서를 인덱스 삼아 배열로 만들어서 확인하는 방법으로 다시 문제를 해결하였다.

 

□ 성공한 코드

#include <bits/stdc++.h>

using namespace std;

int R1987, C1987;
vector<vector<char>> input1987(21,vector<char>(21,NULL));
vector<char> alphabetCheck1987(27,NULL);
int result1987 = 0;

void backback1987(int x, int y, int count){
    int dx[] = {0,0,1,-1};
    int dy[] = {1,-1,0,0};

    for(int i=0;i<4;++i){
        int mx = dx[i] + x;
        int my = dy[i] + y;

        if(mx<1 or mx>R1987 or my<1 or my>C1987)
            continue;

        if(!alphabetCheck1987[input1987[x][y] - 'A']){
            alphabetCheck1987[input1987[x][y] - 'A'] = true;

            result1987 = max(result1987,count);
            backback1987(mx, my, count+1);
            alphabetCheck1987[input1987[x][y] - 'A'] = false;
        }
    }
}

void alphabet1987(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>R1987>>C1987;
    
    for(int i=1;i<=R1987; ++i){
        for(int j=1; j<=C1987; ++j){
            char a; cin>>a;
            input1987[i][j] = a;
        }
    }
    

    backback1987(1, 1, 1);
    cout<<result1987<<"\n";
}