백준 1976 : 여행가자

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

1. 접근

• 여러 번 접근할 수 있는 경로에 대해 갈 수 있는지만 파악하면 되므로, DFS와 BFS 모두 상관없지만 반환값을 통해 갈 수 있는지 여부를 빠르게 반환하기 위해 BFS를 쓰려고 한다
• 시간은 2초, N은 200이하, M은 1000이하 이므로 O(N^2) 의 상황까지 문제없다

2. 나의 풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

/*
*@brief start->end 까지 경로로 이동할 수 있는지 BFS로 판단하는 함수

*@param start 시작 노드 인덱스값 (0~n-1)
*@param end 도착 노드 인덱스값
*@param map 연결 정보를 가리키는 배열
*@param n 도시의 개수를 가리키는 값

*@return start->end 까지 이동할 수 있으면 True
*/
bool IsTravable(int start, int end, vector<vector<bool>> map,int n){
	vector<bool> isvisited(n);
	fill(isvisited.begin(), isvisited.end(), false);
	queue<int> q;
	q.push(start);
	isvisited[start] = true;

	while (!q.empty()) {
		int nowpos = q.front();
		q.pop();

		//도착 값에 도달하면 true를 반환
		if (nowpos == end) {
			return true;
		}
		for (int i = 0; i < n; i++) {
			if (map[nowpos][i]&&!isvisited[i]){
				q.push(i);
				isvisited[i] = true;
			}
		}
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	cin >> n >> m;

	vector<vector<bool>> map(n);
	for (int i = 0; i < n; i++) {
		map[i].resize(n);
		for (int j = 0; j < n; j++) {
			bool input;
			cin >> input;
			map[i][j] = input;
		}
	}

	int start, end;
	cin >> start;
	for (int i = 0; i < m-1; i++) {
		cin >> end;
		if (!IsTravable(start-1, end-1, map, n)) {
			cout << "NO\n";
			return false;
		}
		start = end;
	}
	cout << "YES\n";
	return 0;
}