[BOJ] 백준 13023 ABCDE c++ (DFS, 백트래킹)

문제 출처 : https://www.acmicpc.net/problem/13023

13023번: ABCDE

풀이

조건과 같은 친구 관계가 있는지 구하는 문제이다.

DFS로 친구를 찾아가고 중간에 기존에 있었던 친구가 나오면 탐색을 중단하는 백트래킹을 사용하면 된다.

 

친구 추가

a,b가 입력됐을때 a와 b는 서로 친구이므로 a, b 모두 친구 리스트에 push 해준다.

vector<int> v[2001];
vector<bool> check(2001, false);

for(int i = 0; i < M; i++){
    int a, b;
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
    check[a] = true;
    check[b] = true;
}

check는 입력한 사람들만 검사하려고 체크해두는 vector이다.

이제 입력한 사람들을 빈 벡터에 넣어 dfs를 실행한다.

vector<int> list;
for(int i = 0; i < check.size(); i++){
    if(!check[i]) continue;

    list.push_back(i);
    dfs(list);
    list.pop_back();
}

백트래킹

list는 현재 친구 리스트이다. 만약 리스트안에 사람이 서로 다른 5명(A,B,C,D,E)이라면 정답 케이스이다.

따라서 마지막 인덱스(새로 들어온 친구)가 기존 친구리스트에 이미 있다면 탐색을 중지해준다.

만약 없다면, 마지막 인덱스의 친구 목록을 list에 push해 dfs를 이어간다.

void dfs(vector<int> list){
    int now = list.back();
    if(list.size() > 1){
       // 마지막인 새로 추가한 원소므로 check x
       for(int i = 0; i <= list.size() - 2; i++){
            if(list[i] == now)
                return;
       }
       if(list.size() == 5){
            cout << 1 << '\n';
            exit(0);
       }
    }
    for(int i = 0; i < v[now].size(); i++){
        list.push_back(v[now][i]);
        dfs(list);
        list.pop_back();
    }
    return;
}

---

코드

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int> v[2001];
vector<bool> check(2001, false);

void dfs(vector<int> list){
    int now = list.back();
    if(list.size() > 1){
       // 마지막인 새로 추가한 원소므로 check x
       for(int i = 0; i <= list.size() - 2; i++){
            if(list[i] == now)
                return;
       }
       if(list.size() == 5){
            cout << 1 << '\n';
            exit(0);
       }
    }
    for(int i = 0; i < v[now].size(); i++){
        list.push_back(v[now][i]);
        dfs(list);
        list.pop_back();
    }
    return;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;
    for(int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
        check[a] = true;
        check[b] = true;
    }
    vector<int> list;
    for(int i = 0; i < check.size(); i++){
        if(!check[i]) continue;

        list.push_back(i);
        dfs(list);
        list.pop_back();
    }

    cout << 0 << '\n';
    return 0;
}