[DFS] 2422번 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

2422번 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

 

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

 

문제

한윤정과 친구들은 이탈리아로 방학 여행을 갔다. 이탈리아는 덥다. 윤정이와 친구들은 아이스크림을 사먹기로 했다. 아이스크림 가게에는 N종류의 아이스크림이 있다. 모든 아이스크림은 1부터 N까지 번호가 매겨져있다. 어떤 종류의 아이스크림을 함께먹으면, 맛이 아주 형편없어진다. 따라서 윤정이는 이러한 경우를 피하면서 아이스크림을 3가지 선택하려고 한다. 이때, 선택하는 방법이 몇 가지인지 구하려고 한다.

 

입력

첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 이상 나오지 않는다. (1 ≤ N ≤ 200, 0 ≤ M ≤ 10,000)

 

출력

첫째 줄에, 가능한 방법이 총 몇 개 있는지 출력한다.

 

예제 입력

5 3
1 2
3 4
1 3

 

예제 출력

3

 

해결방법

DFS + 백트래킹 으로 모든 경우를 다해보는 완전 탐색 문제이다

시간복잡도는 O(2^200) 이지만

가지치기의 조건이 주어졌으므로 시간초과가 발생하지 않는다

참고 : Ries 님의 블로그

 

문제에서 가지치기(pruning)의 조건으로 아이스크림의 수를 3개로 제한했다

그렇다면 이제 부분 수열을 구한다음 조합 조건에 맞지 않는 것은 탈락시키면 된다

 

처음에는 vector<vector<int>> 로 조합을 입력 받았는데 다른 블로그에서는 2차원 배열로 처리했다

코드가 훨씬 간단해져 수정을 했다

 

 

[변경 전]

// 정답을 찾은 경우
if(cnt == 3){
    for(int i=0; i<selected.size(); i++){
        for(int j=0; j<selected.size(); j++){
            if(i==j) continue;
            
            for(int k=0; k<ban[selected[i]].size(); k++){
                if(ban[selected[i]][k] == selected[j]){
                    return;
                }
            }
        }
    }
    
    ans++;
    return;
}

 

[변경 후]

// 정답을 찾은 경우
if(cnt == 3){
    // 안 좋은 조합이 존재하는지 검사
    for(int i=0; i<selected.size(); i++){
        for(int j=0; j<selected.size(); j++){
            if(i==j) continue;
            
            if(bad[selected[i]][selected[j]]) return;
        }
    }
    
    // 조합이 정상적이라면 경우의 수 +1
    ans++;
    return;
}

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAX 201
#define INF 987654321
using namespace std;

int n,m,ans;
int u,v;

bool visited[MAX];
int bad[MAX][MAX];

vector<int> selected;

void dfs(int ind,int cnt){
    // 정답을 찾은 경우
    if(cnt == 3){
        // 안 좋은 조합이 존재하는지 검사
        for(int i=0; i<selected.size(); i++){
            for(int j=0; j<selected.size(); j++){
                if(i==j) continue;
                
                if(bad[selected[i]][selected[j]]) return;
            }
        }
        
        // 조합이 정상적이라면 경우의 수 +1
        ans++;
        return;
    }
    
    // DFS 탐색
    for(int i=ind; i<=n; i++){
        if(!visited[i]){
            selected.push_back(i);
            visited[i] = true;
            dfs(i+1,cnt+1);
            visited[i] = false;
            selected.pop_back();
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    
    for(int i=0; i<m; i++){
        cin >> u >> v;
        bad[u][v] = 1;
        bad[v][u] = 1;
    }
    
    memset(visited, false, sizeof(visited));
    ans = 0;
    dfs(1,0);
    cout << ans << "\n";
}