백준 13023번 ABCDE - C++ 풀이

---

 

1. 주어진 조건의 ABCDE가 존재하려면 주어진 그래프에 depth가 4 이상인 구간이 있어야 한다.
2. 모든 가능한 DFS를 시도하면서 depth가 4 이상이 되는 경우가 있는지 확인한다.

 

1. 주어진 조건의 ABCDE가 존재하려면 주어진 그래프에 depth가 4 이상인 구간이 있어야 한다.

 주어진 ABCDE의 관계를 나타내면 A -> B -> C -> D -> E이다. 이렇게 5개의 정점이 쭉 연결된 구간이 있다는 것은 그래프의 높이가 4 이상이라는 의미이다.

 

2. 모든 가능한 DFS를 시도하면서 depth가 4이상이 되는 경우가 있는지 확인한다.

 인접한 정점이 여러개일 때 방문 순서에 따라 depth가 달라지기 때문에 모든 경우를 다 시도해보아야 한다. 시작 정점에 따라서도 depth가 달라지기 때문에 각 정점에서 시작하는 모든 경우를 고려해주어야 한다.

 

반응형

---

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

int N, M;
vector<int> adjs[2001];
bool visit[2001];

bool DFS(int curr, int depth) {
    if (depth >= 4) return true;
    visit[curr] = true;
    
    for (int next: adjs[curr]) {
        if (visit[next]) continue;
        if (DFS(next, depth+1)) return true;
    }
    
    visit[curr] = false;
    return false;
}

bool check() {
    for (int i=0; i<N; i++) {
        if (DFS(i, 0)) return true;
    }
    
    return false;
}

int main()
{
    ios_base::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;
        adjs[a].push_back(b);
        adjs[b].push_back(a);
    }
    
    if (check()) cout << 1;
    else cout << 0;
    
    return 0;
}