백준 13023번 ABCDE (C++)

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

 

백트래킹을 연습하기에 좋은 문제이다. 백트래킹은 모든 경로를 검색하며 1번 노드를 방문하고 여기가 아니면 돌아가는 식으로 이뤄지는 알고리즘이다. 코딩테스트에도 빈출이니 철저히 연습해놔야한다. 백트래킹은 완전탐색에 자주 사용되고 유연하게 사용할 수 있어야한다. 

 

이 문제는 결국은 어떤 정점에서 시작할 때 시작하여 최대 노드의 개수가 자신을 포함해 5개라면 정답이된다. 가지를 쳐내면 된다.

 

그런데 사실 이렇게 생각을 처음에는 했지만 이러면 결국 모든 정점에서 백트래킹을 해야하는데... 시간초과가 안날수가 없는데 안나더라...? 대체 왜 안나는 걸까

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> graph[2001];

bool visited[2001] = {false,};

bool flag = false;

void backtracking(int node, int cnt){
    visited[node] = true;

    if(cnt == 4){
        flag = true;
        return;
    }  

    for(int i = 0; i < graph[node].size(); i++){
        int next = graph[node][i];
        int nextCnt = cnt + 1;

        if(visited[next]) continue;

        visited[next] = true;
        backtracking(next, nextCnt);
        visited[next] = false;
    }
}

int main(){
    int N, M;
    cin >> N >> M;

    for(int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;

        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    for(int i = 0; i < N; i++){
        //if(visited[i]) continue;
        backtracking(i, 0);
        visited[i] = false;

        if(flag) {
            cout << 1 << '\n';
            return 0;
        }
    }

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