부트캠프 5일차 후기

오늘로 부트캠프 1주차가 마무리 되었다. 동시에 미니 프로젝트를 마치고 발표까지 하였다. 관련 후기는

 

https://sumserv.tistory.com/6

1주차 미니 프로젝트 회고

여기 남긴다.

 

사실 오늘은 발표준비를 하고 가다듬은 것 정도가 다고, 프로젝트를 마무리하는 과정에서 시간이 남아서 내가 풀었던 알고리즘 문제 풀이를 간단하게 하려 한다.

 

 

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

16964번: DFS 스페셜 저지

 

알고리즘: DFS, Sort

 

이 문제를 풀기 위해 나는 처음에 트리의 높이를 비교하는 방식을 떠올렸으나 너무 추상적으로 생각했고. 다른 각도로 문제를 생각하게 된다.

 

그리고 생각 끝에 중요한 것은 트리의 탐색 순서란 아이디어가 떠오른다. 그럼 해당 탐색 순서가 되도록 각 인접 리스트를 Sort하고, 트리를 DFS로 순회하자! 란 결론을 내린다. Sort를 위한 비교 함수는 입력에서 주어진 순서를 사용하고, 정렬 뒤의 트리를 DFS를 했을 때, 순회하는 값이 입력 값과 일치하면 1, 아니면 0을 출력한다.

이런 식 흐름대로 아이디어를 떠올렸고, 코드를 구현하였다.

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

const int MAX = 100001;
vector<int> adj[MAX];
int N, D[MAX], A, B, idx = 0, ans = 1, S[MAX];
bool v[MAX];
bool cmp(int a, int b)
{
	return S[a] < S[b];
}
void dfs(int here)
{
	if (D[idx] != here)
	{
		ans = 0;
		return;
	}
	for (int i = 0; i < adj[here].size(); i++)
	{
		int there = adj[here][i];
		if (v[there]) continue;
		v[there] = true;
		++idx;
		dfs(there);
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N - 1; i++)
	{
		cin >> A >> B;
		adj[A].push_back(B);
		adj[B].push_back(A);
	}
	for (int i = 0; i < N; i++)
	{
		cin >> D[i];
		S[D[i]] = i;
	}
	for (int i = 1; i <= N; i++)
		sort(adj[i].begin(), adj[i].end(), cmp);
	v[1] = true;
	dfs(1);
	cout << ans << '\n';
}

이로써 한 문제를 풀었다!