[C++] BOJ 13023 ABCDE

문제

백준 13023번 ABCDE https://www.acmicpc.net/problem/13023

13023번: ABCDE

코드

#include<iostream>
#include<vector>
using namespace std;

int n, m;
vector<int> v[2001];
bool visited[2001];
bool res=false;

void init(){
    for(int i=0; i<2001; i++) visited[i]=false;
}

void dfs (int node, int cnt){
    if (cnt == 5){
        res = true;
        return;
    }
    visited[node]=true;
    for (int i = 0; i < v[node].size(); i++){
        int next = v[node][i];
        if(!visited[next]) dfs(next, cnt + 1);
    }
    visited[node]=false;
}

int main (){
    cin >> n >> m;
    while (m--){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=0;i<n; i++){
        init();
        dfs(i,1);
        if(res) break;
    }
    if(res)cout<<'1';
    else cout<<'0';
}

풀이방법

   깊이우선탐색을 이용한다. 무방향그래프이므로 친구 a,b의 연결이 주어졌을 때, 양쪽을 전부 push_back으로 연결해준다. 이후 main함수에서는 모든 사람(노드) n명에 대하여 dfs함수를 호출한다. dfs를 호출할 때마다 이동한 노드의 번호와 호출 횟수를 넘겨주며, 호출 횟수가 5회가 되는 경우 함수 수행을 중단하며 res값을 true로 바꾸어준다. 마지막으로 res값에 따라서 1 또는 0을 출력해준다.

고민과정

  처음에는 유니온파인드로 풀려고 했다가 dfs가 더 빠를 것 같아서 dfs로 갈아탔다.

  오랜만에 깊이우선탐색을 구현했더니 visited 배열의 값을 언제 다시 false로 바꿔야 할 지 헷갈렸다.