글 읽기 - [시간초과] 개선 방향을 모르겠습니다.

sunio00000 4년 전 0

DFS를 이용해서 가지치기한 경로를 제외한 모든 경로를 탐색하는 목적으로 코드를 작성했습니다.

재귀에서 벡터의 선언때문에 느려지는 걸까요?

아 혹은 반례가 있을 수도 있어 계속 찾아보겠습니다..

봐주신 선생님들 미리 감사합니다.

#include<iostream>
#include<vector>
#include<queue>
#include<utility>
using namespace std;
// 10 10
// ASWERHGCFH
// QWERHDLKDG
// ZKFOWOHKRK
// SALTPWOKSS
// BMDLKLKDKF
// ALSKEMFLFQ
// GMHMBPTIYU
// DMNKJZKQLF
// HKFKGLKEOL
// OTOJKNKRMW
int r,c, ret = 1;
char input;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
vector<vector<char>> vvc;
void DFS(int sx, int se, int depth, vector<bool> v,vector<vector<bool>> vv){
    if(sx < 0 || se < 0 || sx>=c || se >=r) return;
    else if(vv[se][sx]) return;
    else if(v[vvc[se][sx]]) return;
    else{
        v[vvc[se][sx]] = true;
        vv[se][sx]= true;
        for(int i=0; i<4; ++i){
            DFS(sx+dx[i], se+dy[i], depth+1,v,vv);
        }
        ret = max(ret, depth);
    }
}
int main(){
    scanf("%d %d",&r,&c);
    vvc = vector<vector<char>>(r, vector<char>(c));
    vector<bool> visit(150,false);
    vector<vector<bool>> visited= vector<vector<bool>>(r, vector<bool>(c,false));
    for(int i=0; i<r; ++i){
        for(int j=0; j<c; ++j){
            scanf("%c", &input);
            if(input=='0' || input ==' ' || input=='\n') {
                j--;
                continue;
            }
            vvc[i][j] = input;
        }
    }
    DFS(0, 0, 1,visit,visited);
    printf("%d", ret);
    return 0;
}

djm03178 4년 전 1

"재귀에서 벡터의 선언때문에 느려지는 걸까요?"

네, 이것이 매우 느립니다. 구체적으로는 벡터를 값으로 넘겨주면 호출할 때마다 내용물을 전부 복사해야 하기 때문에 느립니다. 참조자로 넘겨주거나 그냥 전역 변수로 두는 것이 낫습니다.

sunio00000 4년 전 0

답변 너무 감사합니다. 참고하여 소스를 수정해보도록 하겠습니다!

sunio00000 4년 전 0

@djm03178 님 감사합니다.

말씀하신대로 수정하여 AC되었습니다.

해결됨!

#include<iostream>
#include<vector>
#include<queue>
#include<utility>
using namespace std;
// 10 10
// ASWERHGCFH
// QWERHDLKDG
// ZKFOWOHKRK
// SALTPWOKSS
// BMDLKLKDKF
// ALSKEMFLFQ
// GMHMBPTIYU
// DMNKJZKQLF
// HKFKGLKEOL
// OTOJKNKRMW
int r,c, ret = 1;
char input;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
vector<bool> visit(150,false);
vector<vector<bool>> visited;
vector<vector<char>> vvc;
// void DFS(int sx, int se, int depth, vector<bool> v, vector<vector<bool>> vv){
//     if(sx < 0 || se < 0 || sx>=c || se >=r) return;
//     else if(v[vvc[se][sx]] || vv[se][sx]) return;
//     // else if(vv[se][sx]) return;
//     else{
//         v[vvc[se][sx]] = true;
//         vv[se][sx] = true;
//         for(int i=0; i<4; ++i){
//             DFS(sx+dx[i], se+dy[i], depth+1,v ,vv);
//         }
//         ret = max(ret, depth);
//     }
// }
void DFS(int sx, int se, int depth){
    if(sx < 0 || se < 0 || sx>=c || se >=r) return;
    else if(visit[vvc[se][sx]]) return;
    else if(visited[se][sx]) return;
    else{
        visit[vvc[se][sx]] = true;
        visited[se][sx]= true;
        for(int i=0; i<4; ++i){
            DFS(sx+dx[i], se+dy[i], depth+1);
        }
        visit[vvc[se][sx]] = false;
        visited[se][sx] = false;
        ret = max(ret, depth);
    }
}
int main(){
    scanf("%d %d",&r,&c);
    vvc = vector<vector<char>>(r, vector<char>(c));
    visited= vector<vector<bool>>(r, vector<bool>(c,false));
    for(int i=0; i<r; ++i){
        for(int j=0; j<c; ++j){
            scanf("%c", &input);
            if(input=='0' || input ==' ' || input=='\n') {
                j--;
                continue;
            }
            vvc[i][j] = input;
        }
    }
    // 경로 탐색, 지나간 길은 체크
    // 전체 경로 탐색 but backtracking 으로 효율성 챙기기
    // DFS(0, 0, 1,visit,visited);
    DFS(0, 0, 1);
    printf("%d", ret);
    return 0;
}

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

문제

문제

출처

ICPC

[시간초과] 개선 방향을 모르겠습니다.

sunio00000 4년 전 0

djm03178 4년 전 1

sunio00000 4년 전 0

sunio00000 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말