글 읽기 - 이 코드의 차이점이 모르겠습니다.

yoonfy4280 4년 전 0

일단 읽어주셔서 감사합니다.

사실 이 문제를 제가 스스로 생각해서 풀지 못했습니다.

해설을 봐도 이해가 아직 안 가는 부분이 있습니다.

일단 해설을 봐도 이해가 안 가는 부부은 왜 꼭 높이에 대한 이동을 -1,0,1 로 고정해야 정답으로 나옵니다.

위로 부터 차근히 파이프를 연결 하여 갯수를 계산 한다는 의미인데, 왜 이런 방식이 정답을 보장하는지 이해가 안됩니다.

( 저는 당연히 마지막 위에서 부터 파이프의 연결이 정답을 보장 못 할 거라고 생각해서 배제 하였는데,, 이게 정답이라서,,, 왜 그런지 모르겠습니다. )

두번째를 두 코드가 사실상 같은데 왜 틀렸다고 나왔는지 모르겠습니다.

틀린 코드 일 경우에, flag=1이 된다면 다음 재귀를 돌리지 않겠다고 하는 건데,,, 이건 DFS()의 반환이 true일 때, 재귀를 돌지 않는 다는 거랑 같은거 같은데

어떤 부분에서 의미적 차이가 있는지 모르겠습니다.

다시 한번 읽어주셔서 감사합니다.

//=> 틀린코드 : flag를 사용하여 탐색 지속 여부를 판단

#include <iostream>
#include <vector>

using namespace std;

int R,C;
int UD[3] = {-1,0,1};

int visited[10000][500] = {0};
char map[10000][500] = {0};

int anw = 0;
int flag;

void DFS(int x, int y,int start){
    
    if(x == C-1 && flag ==0){
        flag = 1;
        anw++;
        
    }
    else{
        
        for(int i = 0; i<3; i++){
            
            int next_x = x +1;
            int next_y = y + UD[i];
            
            if(next_x>=0 && next_x<C && next_y>=0 && next_y<R){
                
                if(map[next_y][next_x] == '.' && visited[next_y][next_x] == 0 && flag == 0){
                    
                    visited[next_y][next_x] = 1;
                    
                    DFS(next_x,next_y,start);
                    
                }
                
            }
            
        }
        
    }
        
    
}

int main(int argc, const char * argv[]) {
    
    cin >> R>> C;

    for(int i = 0; i< R; i++){
        
        for(int j = 0; j<C; j++){
    
            scanf("%c", &map[i][j]);
            
        }
        
    }
    
    for(int i=0;i<R;i++){
        visited[i][0] = 1;
        flag = 0;
        DFS(0, i,i);
    }
    
    cout << anw;

    return 0;
}


//=>맞은 코드 : DFS()의 반환을 보고 탐색 지속 여부 판단

#include <iostream>
#include <vector>

using namespace std;

int R,C;
int UD[3] = {-1,0,1};

int visited[10000][500] = {0};
string map[10000];

int anw = 0;
int flag;

int DFS(int x, int y){
    
    if(x == C-1){
        anw++;
        return true;
    }
    else{
        
        for(int i = 0; i<3; i++){
            
            int next_x = x +1;
            int next_y = y + UD[i];
            
            if(next_x>=0 && next_x<C && next_y>=0 && next_y<R){
                
                if(map[next_y][next_x] == '.' && visited[next_y][next_x] == 0){
                    
                    visited[next_y][next_x] = 1;
                    
                    if(DFS(next_x,next_y) == 1){
                        return true;
                    }
                    
                }
                
            }
            
        }
        
    }
        
    return false;
}

int main(int argc, const char * argv[]) {
    
    cin >> R>> C;

    for(int i = 0; i< R; i++){
        
        cin >> map[i];
        
    }
    
    for(int i=0;i<R;i++){
        visited[i][0] = 1;
       DFS(0, i);
    }
    
    cout << anw;

    return 0;
}

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