[백준] 1976-여행 가자(C++)

문제링크: https://www.acmicpc.net/problem/1976

1976번: 여행 가자

골드4인걸 보면 어려운 부분이 있는것 같지만.. 그냥 일반적인 BFS로 해결할 수 있는 문제 

 

접근방식

 

1. 일반적인 BFS를 통해서 도달이 가능한지 확인할 수 있다.

 

문제풀이 

1. vector에 좌표를 표시

2. bfs!

 

아래는 정답코드입니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m;
bool visited[201] = { 0, };
vector <int> vec[201];
int arr[1001] = { 0, };

void bfs() {
	queue <int> que;
	que.push(arr[0]);
	visited[arr[0]] = 1;

	while (!que.empty()) {
		int pos = que.front();
		que.pop();

		for (int i = 0; i < vec[pos].size(); i++) {
			int npos = vec[pos][i];
			if (visited[npos] == false) {
				visited[npos] = 1;
				que.push(npos);
			}

		}

	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for(int i=1;i<=n;i++)
		for (int j = 1; j <= n; j++) {
			int temp;
			cin >> temp;
			if (temp) {
				vec[i].push_back(j);
				vec[j].push_back(i);
			}
		}

	for (int i = 0; i < m; i++)
		cin >> arr[i];

	bfs();

	for (int i = 0; i < m; i++)
		if (visited[arr[i]] == false) {
			cout << "NO" << endl;
			return 0;
		}

	cout << "YES" << endl;
	return 0;
}