BOJ 백준 1976 : 여행 가자

시작하면서

　이번 문제는 너비우선탐색(BFS) 과 관련된 문제이다.

BOJ 1976 - 여행 가자

​

문제 이해

​ 이 문제의 키워드를 나열해보자.

1. 도시의 수는 200이하이다.
2. 여행 계획에 속한 도시들의 수는 1000이하이다.

그렇다. 최대 수가 상대적으로 적기 때문에, 전부 돌면서 확인하면 된다. 로직은 다음과 같다.

1. 여행 경로들을 모두 큐에 넣고, 하나씩 빼면서 여행이 가능한지 경로 탐색을 진행한다.
2. 경로 탐색을 할 때에는 방문한 도시는 방문 체크를 해주면서, 이미 방문한 곳은 다시 방문하지 않도록 한다.
3. 경로 탐색이 성공하면 계속해서 진행하고, 실패하면 탐색을 끝낸다.

​

해결

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool CanTravel(const vector<vector<bool>> &network, int start, int destination)
{
	vector<bool> isVisited(network.size(), false);
	queue<int> q;

	q.push(start);
	isVisited[start] = true;

	while (q.empty() == false)
	{
		int current = q.front();
		q.pop();
		isVisited[current] = true;

		if (current == destination)
		{
			return true;
		}

		for (int i = 1; i < network[current].size(); i++)
		{
			if (isVisited[i] == true)
			{
				continue;
			}

			if (network[current][i] == true)
			{			
				q.push(i);
			}
		}
	}

	return false;
}

int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// sync off

	vector<vector<bool>> network;
	int N, M;

	cin >> N >> M;

	network.resize(N + 1);
	for (int i = 1; i < N + 1; i++)
	{
		network[i].resize(N + 1);
		for (int j = 1; j < N + 1; j++)
		{
			int info;
			cin >> info;

			network[i][j] = ((info == 0) ? false : true);
		}
	}

	queue<int> travelRoute;
	for (int i = 0; i < M; i++)
	{
		int city;
		cin >> city;

		travelRoute.push(city);
	}
	
	bool canTravel = true;
	int start = travelRoute.front();
	travelRoute.pop();	
	while (travelRoute.empty() == false)
	{
		int destination = travelRoute.front();
		travelRoute.pop();

		if (CanTravel(network, start, destination) == false)
		{
			canTravel = false;
			break;
		}

		start = destination;
	}

	cout << ((canTravel == true) ? "YES" : "NO");

	return 0;
}