[PS] 백준 #13023 ABCDE 문제 풀이

[ 문제 풀이 ]

• Problem : 백준 #13023
• 구분 : DFS, Graph
• 난이도 : Gold 5
• 풀이 방법 :
  • 각 친구(사람)을 노드로 보았을 때, 임의의 노드 A, B, C, D, E가 A-B-C-D-E의 그래프 형태를 띄는 경우가 있는지를 묻는 문제입니다.
  • 처음에는 유니온 파인드로 접근해서 부모노드가 같은 노드가 5개 이상 있으면 True로 반환했는데, 생각해보니 길이 5인 그래프 형태가 아니라도 루트에 5개의 자식노드를 가지고 있으면 True를 반환하기 때문에 해당 문제를 유니온 파인드로 풀 수 없다는 결론에 이르렀습니다.
  • 길이가 5인 그래프를 구하기 위해, dfs로 완전탐색을 돌렸는데 시간초과가 났습니다. 최악의 경우 친구(노드)가 N명, 친구 관계(간선)가 N(N-1)/2인데 dfs 완전탐색의 경우 O(N^3)가 되기 때문입니다.
    
    
  • 그래서, 해당 연산을 줄이기 위해 저는 트리의 지름 개념을 이용했습니다. 트리의 지름에 대한 내용은 링크를 걸어놓은 해당 블로그에서 증명과 개념을 자세히 적어놔주셔서 참고하면 좋을 것 같습니다.
  • 트리의 지름 원리에 의해, 특정 한 점에서 가장 먼 노드에서 가장 먼 노드까지의 길이는 언제나 트리의 지름(가장 긴 길이)이 됩니다.
  • 따라서 우리는 모든 노드를 탐색할 필요 없이 특정 한점을 잡아서 가장 먼 노드의 경우의 완전탐색을 돌린 후, 해당 점에서 다시 완전탐색을 끝까지 돌리면 친구 관계가 연속으로 이어지는 최대의 길이를 구할 수 있습니다.
  • 2번째 완전탐색을 구하기 이전에 이미 친구 관계가 연속으로 이어지는 길이가 5이상이라면 더 돌릴 필요가 없이 해당 그래프는 조건을 만족하므로 바로 정답을 출력하게 하면 됩니다.
  • 시간복잡도는 한 노드를 루트로 잡고 완전탐색을 할 때 최악의 경우에 O(N^2)이지만, 길이가 5 이상일 경우 바로 break를 하도록 로직을 짜면 간선 하나 당 재귀를 최대 5번 이내로 돌게 됩니다.따라서 한 노드에 이어져 있는 간선의 개수*(5 미만의 상수) 만큼만 돌면 되기 때문에 O(N)으로 구할 수 있습니다.
    
    
    시간복잡도는 제 뇌피셜로 계산하는 것이기 때문에, 혹시나 오류가 있다면 정정부탁드립니다..! 🙇🏻‍♀️

[ 🤟🏻 Code from ss-won ]

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#define MAX 2000
using namespace std;
int n, m, u, v;
int e, len = 0;
vector<int> adj[MAX];
bool visited[MAX];
bool res = false;

void dfs(int start, int l){
    if(l==5) {
        res = true;
        return;
    }
    if(l > len){
        e = start;
        len = l;
    }
    for(int i=0;i<(int)adj[start].size();i++){
        if(!visited[adj[start][i]]){
            if(res) break;
            visited[start] = true;
            dfs(adj[start][i], l+1);
            visited[start] = false;
        }
    }
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    
    for(int i=0;i<m;i++){
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    fill(&visited[0], &visited[n]+1, false);
    visited[0] = true;
    dfs(0,1);
    
    if(!res){
        fill(&visited[0], &visited[n]+1, false);
        visited[e] = true;
        dfs(e,1);
    }
    
    cout << res;
    return 0;
}