[BOJ/백준][Gold5] 13023 : ABCDE (C++)

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

13023번: ABCDE

 

 

[난이도] Gold5
[유형] DFS

[풀이]
친구관계를 이용해 그래프를 만들어 준 뒤, 0~N-1의 모든 점에서 dfs를 돌면서 깊이가 5가 되는 경우가 있으면 1을 출력해야 한다. 일반 dfs와 다르게 dfs 함수를 return하기 전에 visit[n]=0 으로 처리를 해줘야 놓치는 케이스 없이 답을 찾을 수 있다.

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int N,M,visit[2001];
vector<int> adj[2001];
bool ok=0;
void dfs(int n,int k){
    if(ok) return;
    visit[n]=1;
    if(k==5) ok=1;
    for(auto nxt : adj[n]){
        if(!visit[nxt]) dfs(nxt,k+1);
    }
    visit[n]=0;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=0;i<N;i++){
        memset(visit,0,sizeof(visit));
        dfs(i,1);
        if(ok) break;
    }
    printf("%d",ok);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/13023.cpp