⭐️ 루트 노드 다음 노드부터 탐색 시작 - 입력 받으면서 탐색하기
⭐️ 연속적으로 증가하는 숫자들은 같은 부모를 갖게 되며 입력받은 수는 무조건 오름차순이기 때문에 앞에 입력받는 수일수록 자식이 먼저 배치될 수밖에 없기 때문에 부모가 될 수 있는 노드는 큐로 관리
⭐️ 이전 노드와 현재 노드의 부모 노드를 변수로 저장해두며 관리
테케는 맞는데 틀렸다고 뜸..
깊이로 사촌을 따지는 것이 아니라 삼촌들의 자식들을 사촌으로 따져야하기 때문에 각 노드의 자식과 부모를 기록해두는 것이 관건이었음
깊이 기록이 아니라 자식 기록으로 방법을 대체
❗️ 최대 개수가 1,000,000 으로 인접리스트로 구현하면 너무 크기 때문에 int 형을 key 로 하고 vector
을 value 로 하는 map
에 자식을 관리하는 것이 포인트였음 ➡️ 자꾸 out of index 오류남;;
큐로 예비 부모 노드를 기록해두는 것은 좋은 시도였음
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,k;
while(1) {
int parents[1000001]; // 각 노드의 부모 저장
map<int,vector<int>> child; // 각 노드의 자식 저장
int root;
queue<int> q;
memset(parents, 0, sizeof(parents));
child.clear();
cin >> n >> k;
if(n==0 && k==0) break;
cin >> root;
if(k==root) {
cout << 0 << endl; // k가 루트노드이면 사촌이 없음
continue;
}
q.push(root);
int pre=0; // 이전 노드 저장
int par=root; // 현재 노드의 부모 노드 저장
for(int i=1;i<n;i++) {
int cur;
cin >> cur;
// 첫 탐색이거나 현재 노드가 이전 노드와 같은 집합에 속하지 않는 노드이면 현재 노드의 부모 갱신
if(pre==0 || pre+1!=cur) {
par=q.front();
q.pop();
}
parents[cur]=par; // 현재 노드의 부모 저장
// 부모의 자식에 현재 노드 저장
vector<int> v;
if(child.count(par)>0) v=child[par];
v.push_back(cur);
child[par]=v;
q.push(cur);
pre=cur;
}
int ans=0;
par=parents[k];
int grand=parents[par];
vector<int> v;
v=child[grand]; // 삼촌 vector
for(int i=0;i<v.size();i++) {
int c=v[i]; // 삼촌 노드
if(c==par) continue;
ans+=child[c].size();
}
cout << ans << endl;
}
}
좋은 정보 얻어갑니다, 감사합니다.