[G4] 백준 25195번 Yes or yes C++ 너비 우선 탐색, 방향 비순환 그래프

리뷰

 

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

1번 노드에서 출발하여 더 이상 갈 곳이 없을 때 까지 곰곰이를 만나지 않을 수 있는지 여부를 체크하는 문제

 

 

전역 변수

• N : 배열의 최대 길이를 정의할 상수 변수
• n : 정점의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• s : 곰곰이가 존재하는 정점의 개수를 저장할 변수
• sp : 각 노드가 시작 노드로 사용이 가능한지 여부를 저장할 배열
• fv : 곰곰이가 존재하는 정점 정보를 저장할 배열
• edges : 인접 리스트 정보를 저장할 벡터 배열

 

함수

1. bfs

bool bfs(int sn) {
	queue<int> q;
	q.push(sn);
	vector<bool> v(n + 1, false);
	v[sn] = true;

	while (!q.empty()) {
		int cn = q.front(); q.pop();
		if (cn == 1) return true;

		for (int nn : edges[cn]) {
			if (v[nn] || fv[nn]) continue;
			v[nn] = true;
			q.push(nn);
		}
	}
	return false;
}

 

현재 노드에서 1번 노드까지 곰곰이를 만나지 않고 이동할 수 있는지 여부를 체크하기 위한 함수

 

 

문제풀이

1. n, m값을 입력 받고, m개의 간선 정보를 초기화 하기 위해 매 루프마다 변수 a, b에 정점의 번호를 입력 받는다.
2. b -> a로 가는 정점을 추가하고, sp[a]는 true로 표시하여 시작 노드가 될 수 없음을 명시해 준다.
3. s값을 입력 받고, s개의 팬클럽 곰곰이가 있는 노드 번호를 입력 받아 fv배열에 true로 저장해 준다.
4. 1~n번 노드를 순회하고 sp[i] 혹은 fv[i]가 true라면 팬클럽 곰곰이가 있거나 말단 노드가 아니므로 continue해준다.
5. 위 조건에 해당하지 않는다면 bfs함수에 현재 노드를 매개변수로 전달해 준다.
6. bfs함수는 전달 받은 매개 변수를 sn으로 받고, 정수형 큐 q를 초기화 해준다.
7. q에 sn을 psuh해주고, n+1크기의 방문 배열 v를 초깃값 false로 초기화, v[sn]을 true로 저장해 준다.
8. q가 빌때까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내 변수 cn에 파싱해 준다.
9. 기저 조건으로 cn이 1일경우 true를 리턴하고, 아니라면 cn의 인접 리스트 edges[cn]를 순회해 준다.
10. 인접 노드 nn에 대해 v, fv배열의 nn값이 true라면 continue처리해 준다.
11. 위 조건에 해당하지 않는다면 v배열에 방문표시 후 q에 nn을 push해준다.
12. while루프가 종료되기 전까지 기저조건에 도달하지 못했다면 false를 리턴해 준다.
13. 만약 bfs함수의 리턴값이 true라면 "yes"를 출력하고 main함수를 종료해 준다.
14. 모든 노드를 돌 때 까지 bfs함수의 리턴값이 true가 아니였다면 "Yes"를 출력하고 main함수를 종료해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 노드 1에서 출발하는 모든 케이스를 찾기 보단 말단 노드에서 팬클럽 곰곰이를 만나지 않으며 1번 노드로 갈 수 있는지 여부를 판단해 주었다.
2. 그로 인해 간선 정보를 역방향으로 설계해 주었다.
3. 팬클럽 곰곰이가 있는 노드는 고정적으로 방문을 기록해 주어 시작, 경유하지 못하게 하였다.
4. 말단 노드 여부는 팬클럽 곰곰이가 아니면서 자신으로 부터 인접한 방향 간선이 없는 경우만 지정해 주었다.

 

정답 코드

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

const int N = 1e5 + 1;
int n, m, s;
bool sp[N];
bool fv[N];
vector<int> edges[N];

bool bfs(int sn) {
	queue<int> q;
	q.push(sn);
	vector<bool> v(n + 1, false);
	v[sn] = true;

	while (!q.empty()) {
		int cn = q.front(); q.pop();
		if (cn == 1) return true;

		for (int nn : edges[cn]) {
			if (v[nn] || fv[nn]) continue;
			v[nn] = true;
			q.push(nn);
		}
	}
	return false;
}

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

	cin >> n >> m;
	while (m--) {
		int a, b; cin >> a >> b;
		sp[a] = true;
		edges[b].push_back(a);
	}

	cin >> s;
	while (s--) {
		int a; cin >> a;
		fv[a] = true;
	}

	for (int i = 1; i <= n; ++i) {
		if (sp[i]) continue;
		if (fv[i]) continue;
		if (bfs(i)) {
			cout << "yes";
			return 0;
		}
	}
	cout << "Yes";
	return 0;
}