[C++] 백준 25195번: Yes or yes

문제 링크

25195번: Yes or yes

문제 요약

투어리스트 곰곰이가 여행을 떠나는데, 중간중간에 팬클럽 곰곰이가 잠복해 있다. 팬클럽 곰곰이를 만나지 않고 여행을 할 수 있는 경로가 있는지 확인해야 한다.

접근 방법

팬클럽 곰곰이가 있는 정점들을 visited 배열에 표시해두고 기존의 BFS와 동일하게 구현만 해주면 됩니다. 매 정점을 방문할 때마다, 방문한 정점에 진출간선이 존재하는지를 확인해줍니다. 만약 존재하지 않는다면, 팬클럽 곰곰이를 만나지 않고 여행을 종료한 것이라고 볼 수 있습니다.

출발 정점에 팬클럽 곰곰이가 있는 경우만 예외로 처리해주면 쉽게 풀 수 있습니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 100001;
int n, m, s;
vector<int> adj[MAX];
bool visited[MAX];

bool bfs(void) {
	if (visited[1])
		return false;

	queue<int> q;
	q.push(1);
	visited[1] = true;

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

		if (adj[now].size() == 0)
			return true;

		for (auto& next : adj[now]) {
			if (!visited[next]) {
				visited[next] = true;
				q.push(next);
			}
		}
	}

	return false;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
	}

	cin >> s;
	
	for (int i = 0; i < s; i++) {
		int fan;
		cin >> fan;
		visited[fan] = true;
	}

	cout << (bfs() ? "yes" : "Yes") << '\n';
	return 0;
}