[G3] 백준 16964번 DFS 스페셜 저지 C++ 깊이 우선 탐색, unordered_set

리뷰

 

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

왜 자꾸 DivisionByZero에러가 뜨지? 라고 생각했는데 결국 인덱스 참조 범위를 벗어난게 문제였다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• v : 방문 여부를 체크할 배열
• edges : 간선 정보를 저장할 unordered_set 배열
• path : 탐색 노드 순서를 저장할 벡터
• idx : 탐색 노드의 인덱스를 저장할 변수

 

함수

1. dfs

void dfs(int cn) {
	if (idx + 1 >= n) return;
	v[cn] = true;

	for (int i = 0; i < edges[cn].size(); ++i) {
		if (idx + 1 >= n) break;
		int nn = path[idx + 1];
		if (!edges[cn].count(nn)) continue;
		if (v[nn]) continue;
		++idx;
		dfs(nn);
	}
}

 

깊이 우선 탐색을 통해 path가 올바른 탐색 경로인지를 체크하기 위한 함수

 

 

문제풀이

1. n값을 입력 받고, n-1개의 간선 정보를 입력 받아 edges배열을 초기화한다.
2. n개의 노드 탐색 순서를 입력 받아 path벡터를 초기화한다.
3. dfs함수에 1을 매개변수로 전달하여 호출한다.
4. dfs함수 내부에선 변수 cn에 매개변수를 파싱하여 저장한다.
5. 기저 조건으로 idx + 1이 n이라면 리턴 처리한다.
6. v[cn]에 방문체크를 한 뒤 edges[cn]의 크기만큼 for문을 개행한다.
7. 만약 idx + 1이 n이상이라면 break처리한다.
8. 변수 nn을 path[idx+1] 값으로 저장한다.
9. edges[cn]에 nn이 없다면 continue처리한다.
10. v[nn]이 이미 방문처리 되어 있다면 continue처리한다.
11. 위 조건에 해당하지 않으면 idx를 증가시키고, dfs함수에 nn을 매개변수로 전달하여 호출한다.
12. 모든 탐색을 마친 후 idx가 n-1이라면 1을, 아니라면 0을 출력한다.

 

트러블 슈팅

1. N값을 10만으로 설정했으나 1-based-indexing이므로 노드가 10만개 일 경우 WA를 받았다.
2. dfs마다 ++idx로 n을 체크해 주었으나, 매번 dfs마다 idx가 증가되는 경우가 있어 WA를 받았다.
3. N을 10만+1로, idx를 탐색 순서가 일치하는 가능한 경우만 증가시키게 로직을 변경하여 AC를 받았다.

 

참고 사항

1. 간선 정보는 양방향 그래프를 기준으로 주어진다.
2. 탐색 시 노드 순서를 상관없이 순회를 하기 위해 unordered_set를 사용해, 간선의 순서를 상관 없게끔 보장해주었다.

 

정답 코드

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

const int N = 1e5 + 1;
int n;
bool v[N];
unordered_set<int> edges[N];
vector<int> path;
int idx;

void dfs(int cn) {
	if (idx + 1 >= n) return;
	v[cn] = true;

	for (int i = 0; i < edges[cn].size(); ++i) {
		if (idx + 1 >= n) break;
		int nn = path[idx + 1];
		if (!edges[cn].count(nn)) continue;
		if (v[nn]) continue;
		++idx;
		dfs(nn);
	}
}

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

	cin >> n;
	for (int i = 0; i < n - 1; ++i) {
		int a, b; cin >> a >> b;
		edges[a].insert(b);
		edges[b].insert(a);
	}
	
	for (int i = 0; i < n; ++i) {
		int a; cin >> a;
		path.push_back(a);
	}

	dfs(1);
	cout << (idx == n - 1 ? 1 : 0);
}