[C++] 13023 ABCDE

 

13023번: ABCDE

 

 

어려운 문제는 아니었는데 문제 이해 잘못 해서 엄청 헤맸다. 사람이 N명이면 depth가 N-1개 있을 경우 1을 반환하는 것으로 이해했는데, 그냥 5명만 연결되어 있으면 (depth=5이면) 해결되는 문제였다. DFS로 백트래킹 이용하면 쉽게 풀림!

 

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

int N,M; //N-사람수 M-관계수 
int visited[2001] = {0,};
vector<vector<int>> relation;
bool flag = false;

void solve(int idx, int depth){
    //조건을 만족한 경우 true 
    if(depth == 5){
        flag = true;
        return;
    }
    for(int i : relation[idx]){
        if(visited[i]==0 && flag==false){
        	//순회 -> 막히면 다시 돌아와 다른 라인 순회 
            visited[i] = 1;
            solve(i,depth+1);
            visited[i] = 0;
        }
    }
}

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

    relation.resize(2001);
    for(int i=1; i<=M; i++){
        int a, b;
        cin>>a>>b;
        //이중 배열 이용 
        relation[a].push_back(b);
        relation[b].push_back(a);
    }

    for(int i=0; i<N; i++){
        if(!flag){
            visited[i] = 1;
            solve(i,1);
            visited[i] = 0;
        }
    }
    //결과 출력 
    cout<<flag;
}