[코드트리] 연결 관계

[문제]

https://www.codetree.ai/problems/connection?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

[문제 풀이]

문제 유형이 BFS로 되어 있지만 DFS를 활용한 백트래킹에 더 가까웠던 문제.

visited 배열을 만든 뒤에 방문한 곳의 위치를 1로 바꾸고 백트래킹을 한 후에 다시 0으로 바꾸기만 하면 어렵지 않게 풀 수 있다.

[회고]

main 함수쪽에서 백트래킹을 돌리는데 자기자신의 방문체크를 안했다가 테스트케이스 6번에서 틀렸었다.

자기 자신도 방문체크를 처음에 해야하는것을 잊지 말자.

[코드]

#include <iostream>
#include <vector>

using namespace std;

bool answer = false;
int n,m;
int arr[2001][2001];
int visited[2001];

void backTrack(int cnt, int len){

    if(len == 5){
        answer = true;
        return;
    }

    for(int i = 0;i<n;i++){
        if(arr[cnt][i] == 1){
            if(visited[i] == 0){
                visited[i] = 1;
                backTrack(i, len + 1);
                visited[i] = 0;
            }
        }
    }
    return;
}

int main() {
    // 여기에 코드를 작성해주세요.
    //1. 양방향으로 이루어져있다.
    //2. 백트래킹을 이용해서 간선의 길이가 5가 되는지 체크하자.
    //3. 2차원배열로 배열로 만들기. / vector<int> arr[2000] arr[0].push_back(1)
    cin>>n>>m;
    for(int i = 0;i<m;i++){
        int a,b;
        cin>>a>>b;
        arr[a][b] = 1;
        arr[b][a] = 1;
    }
    for(int i = 0;i<n;i++){
        visited[i] = 1;
        backTrack(i,1);
        visited[i] = 0;
        if(answer == true)
            break;
    }
    (answer == false) ? cout<<0<<endl : cout<<1<<endl;

    return 0;
}