[백준,c++] 9489번 - 사촌

문제

9489번: 사촌

 

코드

#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;

int graph[1000001];
vector<int> idx;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k;
    while(cin>>n>>k){
        if(n==0 && k==0) break;
        
        int parent_idx = -1, before = 0, ans = 0;
        for(int i=0; i<n; i++){
            int inp; cin>>inp;
            idx.push_back(inp);
            
            if(i==0){
                before = inp;
                graph[inp] = inp;
            }
            else{
                if(before+1 == inp){
                    graph[inp] = idx[parent_idx];
                    before = inp;
                }
                else{
                    before = inp;
                    graph[inp] = idx[++parent_idx];
                }
            }
        }
        for(int node: idx){
            if(graph[graph[node]] == graph[graph[k]] && graph[node] != graph[graph[k]] && graph[node]!= graph[k] && graph[k] != graph[idx[0]]) ans++;
        }     
        cout<<ans<<'\n';
        idx.clear();
        memset(graph,0,sizeof(graph));      
    }   
}

 

풀이

입력이 조금 까다롭게 들어와서 입력 처리에 꽤 공을 들였던 문제였습니다. 

입력만 처리해주면 그 이후는 어렵지않습니다. 사촌 노드란 현실의 뜻 그대로 부모는 다르지만 부모의 부모는 같은 노드를 뜻합니다.

노드(15)의 사촌들

위 이미지에서 15의 사촌 노드들은 부모의 부모가 같은 8, 9, 30, 31, 32가 됩니다.

여기서 주의해야 할 엣지케이스는 3, 4, 5입니다. 3, 4, 5 노드의 경우 사촌이 아니라 삼촌이기 때문에 조건문에서 걸러주어야 합니다.

for(int node: idx){
	if(graph[graph[node]] == graph[graph[k]] && graph[node] != graph[graph[k]] && graph[node]!= graph[k] && graph[k] != graph[idx[0]]) ans++;
}

저는 모든 노드들마다 부모노드를 저장해준 뒤, 위 코드를 통해 사촌인지 판별하여 정답을 구했습니다.