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

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

1976번: 여행 가자

1. 주의할 점

- Node를 Cluster로 묶을 수 있어야 한다

- 중복 방문하는 Node에 대한 처리를 해야 한다

 

2. 구현

- Node에서 다른 Node로 갈 수 있는 정보를 V 벡터에 담는다

- 방문하려는 Node중 1개를 골라서 Queue에 넣고 간선을 타고 이동할 수 있는 모든 Node에 대해 체크해준다

- 큐가 마친후, 방문 하려는 Node가 방문 가능하다고 체크되어 있지 않다면 NO 출력하고 체크되어 있다면 YES를 출력한다

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> v[201];
bool need_visit[201] = { false, };
bool visit[201] = { false, };

int main() {
	int node, m, val, tt = -1;
	cin >> node >> m;
	for (int i = 1; i <= node; i++) {
		for (int j = 1; j <= node; j++) {
			cin >> val;
			if (val == 1) {
				v[i].push_back(j);
				v[j].push_back(i);
			}
		}
	}
	for (int i = 0; i < m; i++) {
		cin >> val;
		if (tt == -1) tt = val;
		need_visit[val] = true;
	}
	queue<int> q;
	q.push(tt);
	visit[tt] = true;
	need_visit[tt] = false;
	while (!q.empty()) {
		int cidx = q.front();
		q.pop();
		for (int i = 0; i < v[cidx].size(); i++) {
			int next = v[cidx][i];
			if (!visit[next]) {
				visit[next] = true;
				q.push(next);
				if (need_visit[next])	need_visit[next] = false;
			}
		}
	}
	bool avail = true;
	for (int i = 1; i <= node; i++) {
		if (need_visit[i]) {
			avail = false;
			break;
		}
	}
	if (avail) cout << "YES";
	else cout <<"NO";
	system("pause");
	return 0;
}