[BOJ]16964번: DFS 스페셜 저지 (c++)

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

16964번: DFS 스페셜 저지

 

 

방법 1: 입력순서대로 인접리스트를 정렬 후 dfs 재귀함수 호출

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX = 100000;
bool visited[MAX + 1];
int test_idx;

// 입력으로 주어진 DFS 방문순서가 올바른지 검사
bool dfs(vector<vector<int>>& graph, vector<int>& test, int now)
{
	// 방문 체크
	visited[now] = true;

	// 입력순서대로 정렬된 각 노드의 인접리스트를 순회
	// 입력순서를 담은 test벡터의 인덱스는 점차 증가한다.
	for (int next : graph[now])
	{
		if (!visited[next])
		{
			// 다음 자식노드와 다음 입력노드가 일치하지 않으면 false반환 및 종료
			if (next != test[++test_idx])
			{
				return false;
			}
			// 일치하면 dfs재귀함수 호출 결과 반환
			else
			{
				return dfs(graph, test, next);
			}
		}
	}

	return true;
}

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

	// 입력
	int N;
	cin >> N;
	vector<vector<int>> graph(N + 1, vector<int>());
	for (int i = 0; i < N - 1; ++i)
	{
		int first, second;
		cin >> first >> second;
		graph[first].push_back(second);
		graph[second].push_back(first);
	}
	// order : 입력순서로 주어진 노드들의 순서정보 
	vector<int> order(N + 1);
	vector<int> test(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> test[i];
		order[test[i]] = i;
	}

	// order의 순서대로 인접리스트 정렬
	for (vector<int>& part : graph)
	{
		sort(part.begin(), part.end(), [&](const int& i, const int& j) {
			return order[i] < order[j];
			});
	}

	// 입력으로 주어진 DFS 방문순서가 올바르면 1, 아니면 0 출력
	cout << dfs(graph, test, 1);

	return 0;
}

 

방법 2: 자식 노드 중에서 다음 입력순서 노드가 나올 때까지 반복해서 찾기

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 100000;
bool visited[MAX + 1];
int test_idx;
bool ok;

// 입력으로 주어진 DFS 방문순서가 올바른지 검사
void dfs(vector<vector<int>>& graph, vector<int>& test, int now)
{
	// 방문체크
	visited[now] = true;

	for (int i = 0; i < graph[now].size();)
	{
		int next = graph[now][i];
		
		// 아직 방문하지 않았고, 다음 입력노드와 일치하는 자식노드
		if (!visited[next] && next == test[test_idx + 1])
		{
			++test_idx;
			dfs(graph, test, next);
			
			// test벡터를 가리키는 인덱스가 끝에 도달했다면 성공. 종료
			if (test_idx >= test.size() - 1)
			{
				ok = true;
				return;
			}
			// dfs재귀함수 호출 후에는 다시 처음부터 반복문을 실행하여
			// 자식 노드 중에서 다음 입력노드를 찾는다.
			i = 0;
		}
		// 위 조건에 해당하지 않으면 인덱스값 증가
		else
		{
			++i;
		}
	}
}

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

	// 입력
	int N;
	cin >> N;
	vector<vector<int>> graph(N + 1, vector<int>());
	for (int i = 0; i < N - 1; ++i)
	{
		int first, second;
		cin >> first >> second;
		graph[first].push_back(second);
		graph[second].push_back(first);
	}
	vector<int> test(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> test[i];
	}

	// 입력으로 주어진 DFS 방문순서가 올바르면 1, 아니면 0 출력
	dfs(graph, test, 1);
	cout << ok;

	return 0;
}

 

bfs스페셜 저지 문제보다 이게 더 어려웠다 ㅜㅜ

 

방법 1이 더 빠르다. 

방법 2는 마지막 자식 노드에 대한 재귀함수 호출이 끝났을 때에도,

일단 재귀함수 호출이 끝났다면

쓸데없이 다시 처음부터 자식노드를 탐색을 반복하는 낭비가 있다.