삼성 코딩테스트 A형 기출문제

문제

백준 17070번: 파이프 옮기기1

코드

Sol1 ) 재귀

#include <iostream>
using namespace std;
int arr[16][16];
int cnt;
int N;
int function(int end_r,int end_c,int direction){
    if(end_r>=N || end_c>=N)
        return 0;
        
    //해당 direction일때 그 direction이 빈칸인지 확인 및 예외처리
    if(direction==0 || direction==1)//가로 또는 세로일 때
        if(arr[end_r][end_c] == 1)
            return 0;
    if(direction==2)
        if(arr[end_r][end_c]==1 || arr[end_r-1][end_c]==1 || arr[end_r][end_c-1]==1)
            return 0;

    //cout<<"end_r : "<<end_r<<" , "<<"end_c : "<<end_c<<"direction : "<<direction<<"\n"; 
    
    if(end_r==N-1 && end_c==N-1){
        //cout<<"The END  end_r :"<<end_r<<", end_c : "<<end_c<<",direction : "<<direction<<"\n";
        cnt++;
        return 0;
    }
    
    if(direction==0){
        function(end_r,end_c+1,0);
        function(end_r+1,end_c+1,2);
    }
    else if(direction==1){
        function(end_r+1,end_c,1);
        function(end_r+1,end_c+1,2);
    }
    else if(direction==2){
        function(end_r,end_c+1,0);
        function(end_r+1,end_c,1);
        function(end_r+1,end_c+1,2);
    }
    
    //cout<<"return end_r : "<<end_r<<","<<"end_c : "<<end_c<<"\n";
    
    return 0;
    
    
}
int main(){
    //파이프를 (N-1,N-1)로 이동시키는 수
    cin>>N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin>>arr[i][j];
        }
    }
    

    function(0,1,0);//end_r,end_c,direction
    //direction은 가로면 0 , 세로면 1 , 대각선이면 2 
    cout<<cnt;
    
    return 0;
    
}

Sol2 ) DFS

#include <iostream>
#include <stack>
#include <tuple>
using namespace std;
int arr[16][16];
int cnt;
int N;
stack<tuple<int,int,int>> myStack;
int main(){
    //파이프를 (N-1,N-1)로 이동시키는 수
    cin>>N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin>>arr[i][j];
        }
    }
    
    myStack.push(make_tuple(0,1,0));
    
    while(!myStack.empty()){
        tuple<int, int, int> values = myStack.top();
        //cout<<"end_r : "<<get<0>(values)<<" end_c : "<<get<1>(values)<<" direction : "<<get<2>(values)<<"\n";
        int end_r = get<0>(values);
        int end_c = get<1>(values);
        int direction = get<2>(values);
        myStack.pop();
        
        if(end_r>=N || end_c>=N)
            continue;
        
        //해당 direction일때 그 direction이 빈칸인지 확인 및 예외처리
        if(direction==0 || direction==1)//가로 또는 세로일 때
            if(arr[end_r][end_c] == 1)
                continue;
        if(direction==2)
            if(arr[end_r][end_c]==1 || arr[end_r-1][end_c]==1 || arr[end_r][end_c-1]==1)
                continue;
    
        //cout<<"end_r : "<<end_r<<" , "<<"end_c : "<<end_c<<"direction : "<<direction<<"\n"; 
        
        if(end_r==N-1 && end_c==N-1){
            //cout<<"The END  end_r :"<<end_r<<", end_c : "<<end_c<<",direction : "<<direction<<"\n";
            cnt++;
            continue;
        }
        
        
        
        if(direction==0){
            myStack.push(make_tuple(end_r,end_c+1,0));
            myStack.push(make_tuple(end_r+1,end_c+1,2));
        }
        else if(direction==1){
            myStack.push(make_tuple(end_r+1,end_c,1));
            myStack.push(make_tuple(end_r+1,end_c+1,2));
        }
        else if(direction==2){
            myStack.push(make_tuple(end_r,end_c+1,0));
            myStack.push(make_tuple(end_r+1,end_c,1));
            myStack.push(make_tuple(end_r+1,end_c+1,2));   
        }
    }
    
    
    
    cout<<cnt;
    
    return 0;
    
}

트러블 슈팅

#include <iostream>
using namespace std;
int arr[16][16];
int cnt;
int N;
int function(int end_r,int end_c,int direction){
    
    if(end_r==N-1 && end_c==N-1){
        //cout<<"The END  end_r :"<<end_r<<", end_c : "<<end_c<<",direction : "<<direction<<"\n";
        cnt++;
        return 0;
    }
    
    if(end_r>=N || end_c>=N)
        return 0;
        
    //해당 direction일때 그 direction이 빈칸인지 확인 및 예외처리
    if(direction==0 || direction==1)//가로 또는 세로일 때
        if(arr[end_r][end_c] == 1)
            return 0;
    if(direction==2)
        if(arr[end_r][end_c]==1 || arr[end_r-1][end_c]==1 || arr[end_r][end_c-1]==1)
            return 0;

    //cout<<"end_r : "<<end_r<<" , "<<"end_c : "<<end_c<<"direction : "<<direction<<"\n"; 
    
    
    if(direction==0){
        function(end_r,end_c+1,0);
        function(end_r+1,end_c+1,2);
    }
    else if(direction==1){
        function(end_r+1,end_c,1);
        function(end_r+1,end_c+1,2);
    }
    else if(direction==2){
        function(end_r,end_c+1,0);
        function(end_r+1,end_c,1);
        function(end_r+1,end_c+1,2);
    }
    
    return 0;
    
    
}
int main(){
    //파이프를 (N-1,N-1)로 이동시키는 수
    cin>>N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin>>arr[i][j];
        }
    }
    

    function(0,1,0);//end_r,end_c,direction
    //direction은 가로면 0 , 세로면 1 , 대각선이면 2 
    cout<<cnt;
    
    return 0;
    
}

해당 코드는 '틀렸습니다'가 뜬 코드이다.
예외처리 순서를 신경 써 주어야 한다.
(N-1,N-1)칸도 벽(1)인지 아닌지 예외처리를 해줘야하므로 순서가 예외처리 후 cnt++를 해야한다.