[BOJ/백준][Gold4] 1976 : 여행 가자 (C++)

www.acmicpc.net/problem/1976

1976번: 여행 가자

 

 

[난이도] Gold4

[유형] DFS

 

[풀이]

여행해야하는 임의의 한 점에서 DFS를 돌았을 때 여행 경로에 있는 모든 점을 Visit한 경우에만 YES이다.

 

 

#include <cstdio>
using namespace std;
int N,M,d[1001];
bool adj[201][201],visit[201];
void dfs(int n){
    visit[n] = 1;
    for(int i=1;i<=N;i++)
        if(adj[n][i] && !visit[i]) dfs(i);
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) scanf("%d",&adj[i][j]);
    for(int i=0;i<M;i++) scanf("%d",&d[i]);
    dfs(d[0]);
    for(int i=0;i<M;i++) {
        if(!visit[d[i]]) {
            puts("NO");
            return 0;
        }
    }
    puts("YES");
}

 

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1976.cpp