백준(boj) 2422 - 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (백트래킹)

문제 링크 - https://www.acmicpc.net/problem/2422

👀문제이해 및 풀이방법

solved.ac기준 실버5인 쉬운 문제이다. 백트래킹을 사용하는 dfs문제인데 visit을 체크하는 기초적 관점에서 얻은게 있어 글을 작성한다.
보통 visit배열로 백트래킹을 체크할 때 bool타입으로 체크해두었다가 푸는 형식을 사용한다. 하지만 이 문제에서는 이런 방식으로 방문을 체크하면 풀리지 않는다. 앞에서 여러개가 방문을 막고 있을 수 있기 때문에 int 타입으로 ++, – 형식으로 방문을 체크해주어야 모든 막힌 부분이 풀렸을 때 방문이 가능해진다. 메모리 낭비를 막기위해 bool형태를 자주 사용하였지만 앞으로는 ++, – 형태로 백트래킹을 체크해야겠다.

📝코드

#include <iostream>
#include <vector>
using namespace std;
class icecream{
private:
    vector<vector<int>> ban;
    vector<int> visit;
    vector<int> test;
    int N,M;
public:
    icecream(){
        std::cin >> N >> M;  
        ban.resize(N+1);
        visit.resize(N+1,0);
        test.resize(3);
        set_val();
    }
    void set_val(){
        int a,b;
        for(int i=0;i<M;i++){
            std::cin >> a >> b;
            if(a>b)
                swap(a,b);
            ban[a].push_back(b);
        }
    }
    int dfs(int cur,int depth){
        if(depth==3)
            return 1;
        
        int sol=0;
        for(int i=cur+1;i<=(N-2+depth);i++){
            if(!visit[i]){
                for(int b : ban[i])
                    visit[b]++;
                sol+=dfs(i,depth+1);
                for(int b : ban[i])
                    visit[b]--;
            }
        }
        return sol;
    }

    void find_sol(){
        std::cout << dfs(0,0)<<'\n';
    }


};
int main(){
    cin.tie(NULL);cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    icecream ic;
    ic.find_sol();

    return 0;
}