728x90

문제 링크 : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

 

 

 

 

접근 방법

재귀를 이용한 DFS로 풀었다. set 자료구조로 삽입시 중복이 되지 않게 했다.

테스트 케이스가 반복되므로 매 테스트케이스가 끝날때마다 초기화를 잘 해줘야 에러가 안 뜬다. 주의하자!

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int map[4][4]={0};

//위,오,아,왼
int dr[4]={-1,0,1,0};
int dc[4]={0,1,0,-1};

vector<int> nVec;
set<int> ansVec;

void DFS(int r, int c, int toPick){
    
   
    if(toPick==0){
        int num = nVec[0]*1000000+nVec[1]*100000+nVec[2]*10000+nVec[3]*1000+nVec[4]*100+nVec[5]*10+nVec[6];
        
        ansVec.insert(num);
        return;
    }
    
    
    for(int i=0; i<4; i++){
        
        int nr=r+dr[i];
        int nc=c+dc[i];
        
        if(nr>=4 || nr<0 || nc>=4 || nc<0) continue;
        
        nVec.push_back(map[nr][nc]);    //next 지점이 범위 안에 들어오면 push
        DFS(nr,nc,toPick-1);
        nVec.pop_back();				//원상복구
    }
}

int main(){

    int T;
    cin >> T;
    
    int ans=0;
    for(int test_case = 1; test_case <= T; test_case++){
        
         for(int i=0; i<4; i++){
           for(int j=0; j<4; j++){
               cin>>map[i][j];
           }
         }
        
        for(int i=0; i<4; i++){
            for(int j=0; j<4; j++){
                nVec.push_back(map[i][j]);          //첫 시작지점 넣음
                DFS(i,j,6);
                nVec.clear();					 //초기화 필수

            }
        }
        
        cout << "#" << test_case << " " << ansVec.size() << "\n";
        
        //초기화 필수
        ans=0;
        ansVec.clear();
        nVec.clear();
        
    }
    
    return 0;
}

 

 

 

 

처음에는 set이 아닌 vector를 이용해서 find()를 통해 중복검사를 했는데 제한시간 2초를 넘겨서 시간초과가 떴다. 그래서 set으로 바꿔봤는데 바로 통과됐다.

if(toPick==0){
        int num = nVec[0]*1000000+nVec[1]*100000+nVec[2]*10000+nVec[3]*1000+nVec[4]*100+nVec[5]*10+nVec[6];
       
        if(find(ansVec.begin(),ansVec.end(),num) == ansVec.end()){
            ansVec.push_back(num);
        }
        return;
}

 

 

728x90

+ Recent posts