[ boj : 1976] 여행 가자

www.acmicpc.net/problem/1976

1976번: 여행 가자

문제 : 동혁이가 가고 싶어하는 도시를 갈 수 있는지 없는지 구하시오

 

해설 : 다른 분들은 disjoint-set 개념을 이용해서 푸셨는데, 전 그냥 dfs 한번 돌렸습니다.

결국 동혁이가 같은 도시를 여러번 방문 하던 안하던 시작점에서 한번 dfs를 돌렸을때 못가는 도시는 평생 가지 못하기 때문이죠.

 

#include<bits/stdc++.h>

using namespace std;

int n,m;
int adj[210][210],arr[210];
int visit[210];

void dfs(int p,int x);

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>adj[i][j];
	for(int i=0;i<m;i++) cin>>arr[i];
	
	dfs(-1,arr[0]);
	for(int i=0;i<m;i++)
		if(visit[arr[i]]==0){
			cout<<"NO";
			return 0;
		}
	cout<<"YES";
	return 0;
}
void dfs(int p,int x)
{
	if(visit[x])return;
	
	visit[x]=1;
	for(int i=1;i<=n;i++){
		if(p==i)continue;
		if(adj[x][i]==1)
			dfs(x,i);
	}
}