백준 - 1976번 : 여행 가자 (C++)

풀이 방법 : DFS

여행 플랜의 첫번째 지점부터 연결된 지점들을 따라서 DFS를 했을 때 플랜에 속해있는 지점들의 check 플래그가 전부 true가 되어있으면 YES를, 하나라도 false가 존재하면 NO를 출력해주는 방식으로 구현했다.

#include <iostream>
#include <vector>

using namespace std;

bool CheckEnable[201] = {};
bool IsConnect[201][201] = {};

void DFS(int Start, int CityCnt)
{
	CheckEnable[Start] = true;

	for (int i = 0; i < CityCnt; ++i)
	{
		if (IsConnect[Start][i])
		{
			if(!CheckEnable[i])
				DFS(i, CityCnt);
		}
	}
}

int main()
{
	int N, M;

	cin >> N >> M;

	vector<int> vecPlan;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			int Connect;
			cin >> Connect;

			IsConnect[i][j] = Connect;
			IsConnect[j][i] = Connect;
		}
	}

	bool Enable = true;

	for (int i = 0; i < M; ++i)
	{
		int Plan;
		cin >> Plan;
		vecPlan.push_back(Plan - 1);
	}

	DFS(vecPlan[0], N);

	for (int i = 0; i < M; ++i)
	{
		if (!CheckEnable[vecPlan[i]])
		{
			Enable = false;
			break;
		}
	}

	if (Enable)
		cout << "YES" << '\n';

	else
		cout << "NO" << '\n';
	
}