13023번 (gold 5)

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

간단하게 재귀함수로 풀어본 문제이다.

 

#include <iostream>
#include <vector>

using namespace std;
static bool arrive = false;
void DFS(const vector<vector<int>>&, int, int);
int main() {
	cin.tie(0)->sync_with_stdio(false);
	int N, E;
	cin >> N >> E;
	vector<vector<int>> arr(N, vector<int>());
	int index = 0;
	for (int i = 0; i < E; ++i) {
		int tmp = 0;
		cin >> index >> tmp;
		arr[index].emplace_back(tmp);
		arr[tmp].emplace_back(index);
	}

	for (int i = 0; i < N; ++i) {
		DFS(arr, i, 1);
		if (arrive == true)
			break;
	}

	if (arrive == true)
		cout << 1;
	else
		cout << 0;

	return 0;
}


void DFS(const vector<vector<int>>& arr, int searchNode, int depth) {
	static vector<bool> visit(arr.size(), false);

	if (visit[searchNode] == true || arrive == true) return;
	if (depth >= 5) {
		arrive = true; return;
	}
	visit[searchNode] = true;

	for (int i = 0; i < arr[searchNode].size(); ++i) {
		DFS(arr, arr[searchNode][i], depth + 1);
	}

	visit[searchNode] = false;
}

 

 이번 문제를 풀면서 DFS에서 visit 배열에서 이미 방문했어도 재귀함수가 끝나기 전에 visit값을 false로 바꾼다는 개념을 체득하였다.

 

 단순하게 visit배열이 한번 방문하면 true로 바뀌고 한번 방문한 곳은 방문하지 않는 완전탐색을 기본으로 생각하고 있었는데, 이 문제에서는 완전탐색을 하는게 아닌 depth가 5이상인 node들의 연결의 있냐를 찾는거기 때문에 만약에 방문한 곳을 true로 바꾸고 함수가 해제되기 전에 false로 바꾸지 않는다면 완전탐색은 될지언정 모든 가능한 edge를 찾은 것은 아니게 되기 때문에 해제되기 전에 false로 visit값을 변경해야한다.

 

 또한 std::vector<bool>은 메모리 값을 아끼기 위해서 bool값을 1byte가 아닌 1bit단위로 사용한다는 것은 알고있었는데,

for(auto& it: visit)을 하니 visit이 우측값이라고 하는 것을 보고 당황하였으나, 찾아보니 std::vector<bool>은 특별한 으로 std::vector<bool>::reference타입을 가지는 것을 알게되었다.

 

 c++은 참조를 1bit단위로 사용할 수 없기 때문에 bool&처럼 작동하는 std::vector<bool>::reference가 사용되고, 우측값인 것으로 보인다.

 

 그래서 for(auto& it: visit)을 for(std::vector<bool>::reference const& it: visit)나 for(auto& const it: visit) 혹은 값을 변경해야 한다면 for(auto&& it: visit)으로 우측값을 받는 &&로 구현하면 된다.