Approach 자료구조 수업에서나 나올법한 문제이다. 잘 생각해보면 preorder가 하는 역할을 잘 생각해보면, 루트 노트부터 시작해서 왼쪽 방향무터 서브트리의 루트노드를 지속적으로 방문하게 된다. 따라서 해당 순서를 inorder에서 바라보게 되면, 발견한 index를 기준으로 왼쪽은 자신을 기준으로 왼쪽과 오른쪽으로 subtree를 나누어서 생각할 수 있다. 세그트리 짜는 것처럼, start, end index를 함수의 입력값으로 두고 계속해서 좁혀가면 쉽게 구할 수 있다. Code #include #define fastio ios_base::sync_with_stdio(0). cin.tie(0), cout.tie(0) using namespace std; vector preorder; vecto..

Approach 트리의 개수는 전체 component 개수에서 사이클을 가지는 component 개수를 제외해주면 된다. Component 개수를 구하는 것은 dfs를 호출하는 횟수와 동일하므로, 사이클이 발생하는지 여부만 체크해주면 된다. 앞에서 풀었던 문제들과 달리 한 정점에서 반드시 사이클을 지시하고 있지는 않은 상황이므로(https://viyoung.tistory.com/327) [백준 10265번] [DFS / SCC] MT Approach 위 문제에서 나타나게 되는 그래프를 잘 관찰해보면 사이클이 반드시 등장하게 되는 것을 관찰할 수 있다. 즉 1개의 Component를 기준으로 사이클이 존재하고 해당 사이클에 속한 노드를 viyoung.tistory.com 무작정 사이클이 나타날때까지 계속해..

처음에 루트노드가 0으로 고정인줄 알고 실수하였다.. 문제 자체는 되게 단순하다. 1. 트리를 구성하고 2. 특정 노드를 끊는다.(위 기준으로 끊으면 어차피 아래에 접근이 안된다.) 즉, parent node를 기준으로 해당 node를 끊어주기만 하면 된다. 다만, 가장 최상단 root node를 제거하는 경우는 따로 예외처리하도록 하자. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; int arr[51][51]; int N; int dfs(int start){ bool check = true; int count = 0; for(int i = 0; i < N; i ++){ ..