[Baekjoon] 5568번: 카드 놓기 (c++)

https://www.acmicpc.net/problem/5568

5568번: 카드 놓기

 

DFS로 사용했던 카드(isVisited[i] = true)는 다시 사용하지 않는 방법으로 구현했다.

 

1. 모든 카드를 뽑는 경우를 생각해서 for문을 카드의 개수 n만큼 반복하며 DFS 실행

2. 처음 뽑은 카드 inp[0]에 대하여 방문 표시 isVisited[0] = true 

     - 카드를 k개만큼 뽑았을 때만 (현재 DFS의 깊이 cnt와 주어진 k(=depth)의 크기가 같을때만) unordered_map 해시맵 card에다 넣어줌

     - 숫자가 같은 카드는 다시 세지 않기 위해 unordered_map 사용함

3. 카드는 숫자 덧셈이아니라 연결하는것이기 때문에 to_string으로 처리해서 연결해준 값을 num에 저장함

4. DFS를 다시 실행할 때는 숫자여야 하므로 다시 stoi(num) 해줌

5. 아직 방문하지 않은 카드에 대해서만 DFS 다시 실행

6. 방문 했던 카드는 DFS 빠져나올 때 isVisited=false 처리 해줘야 다음에도 사용 가능

 

 

---

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

unordered_map<int, int> card;
int result = 0;
int n;
bool isVisited[11] = {false,};
int inp[11] = {0};

void DFS(int V, int depth, int index, int cnt = 1){
    isVisited[index] = true;
    if(cnt == depth){
        card[V] = 1;
        isVisited[index] = false;
        return;
    }
    cnt++;
    for(int i=0;i<n;i++){
        string num = to_string(V) + to_string(inp[i]);
        
        if(!isVisited[i]){
            DFS(stoi(num), depth, i, cnt);
            isVisited[i] = false;
        }
    }
}
int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   
    int k, num;
    cin >> n >> k;
    
    for(int i=0; i<n; i++) {
        cin >> inp[i];
    }
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)isVisited[j]=false;
        DFS(inp[i], k, i);
    }
    
    cout << card.size();
    return 0;
}