[C++] SWEA - 2819. 격자판의 숫자 이어 붙이기 - DFS

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

SW Expert Academy

 

 

 

 

 

접근 방법

재귀를 이용한 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;
}