취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25195번 문제인 Yes or yes이다.
문제는 아래 링크를 확인하자.

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

주어지는 그래프는 DAG이므로, 사이클이 존재하지 않는다는 점을 적극 이용하여 풀이를 간단하게 만들자.

구체적으로 1번 노드에서 출발해 팬클럽 곰곰이를 만나면서 더 아래로 내려갈 수 있는 노드가 없는 노드까지 도달하는 경로가 존재한다면 yes, 그렇지 않다면 YES를 출력하자.

위와 같은 경로는 DFS나 BFS 등의 그래프 탐색 알고리즘으로 쉽게 탐색해볼 수 있다.

아래는 제출한 소스코드이다.

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

bool gomgom[100001];
vector<int> G[100001];
bool ans = 1;

void dfs(int cur) {
	if (G[cur].empty()) ans = 0;
	for (auto& node : G[cur]) {
		if (gomgom[node]) continue;
		dfs(node);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M; cin >> N >> M;
	while (M--) {
		int u, v; cin >> u >> v;
		G[u].emplace_back(v);
	}
	G[0].emplace_back(1);
	int S; cin >> S;
	while (S--) {
		int x; cin >> x;
		gomgom[x] = 1;
	}

	dfs(0);

	if (ans) cout << "Yes";
	else cout << "yes";
}