[백준/C++] 15942번: Thinking Heap(G2)

문제

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

15942번: Thinking Heap

 

 

사용한 알고리즘

2022.02.09 - [PS/Algorithm] - [알고리즘 개념정리] 9. 트리

-> Binary Heap

 

 

풀이 

heap[idx] 배열로 min-heap binary tree를 관리해준다.
1-based로 하면 부모 idx가 i일 때, 자식은 2i 와 2i+1이고 자식 idx가 i일 때, 부모는 i/2이다.

heap[p]=k 인 min-heap 이진트리를 출력하는 것이 목표이므로
일단 heap[p]에 k를 넣고 시작해보자.

k의 조상은 전부 k보다 작은 수이어야 하고, 자손은 전부 k보다 큰 수이어야 한다.
그러므로, k의 부모를 타고 올라가면서 k-1, k-2, ...를 넣어주고, 자식들에게는 k+1, k+2, ...을 넣어주면 된다.
-> 이때, 조상 중 heap[idx]<=0인 노드가 있거나, 자손 중 heap[idx]>n인 노드가 있으면  
    heap[p]=k인 min-heap을 만들지 못한다는 뜻이므로 -1을 출력해준다.

그 후, heap배열에서 아직 채워지지 않은 곳을 채워준다.
위에서 이미 사용한 수를 제외하고, 1부터 N까지의 수들을 차례로 넣어준다.
-> 이때, 부모 중 방금 넣은 수보다 더 큰 수가 있다면 min-heap조건을 만족할때까지 flip해준다.

---

 

<main함수>

1. n, k, p 입력받는다. 
   heap[p]=k인 min-heap을 만드는 것이 최종 목표이다.
2. dfs(p) 함수를 실행한다.
   그 결과, p의 자손들의 heap배열이 채워지고 downnum변수에는 '자손의 heap배열 값 중 max'가 담긴다.
3. while문을 돌며 p의 조상들의 heap배열을 채운다.
   그 결과, upnum변수에는 '조상의 heap배열 값 중 min'이 담긴다.
4. upnum<=0이면 min-heap을 만들지 못한다는 뜻이므로 -1을 출력하고 종료한다.
5. 배열을 순회하며 heap배열이 채워지지 않은 노드들은 insert(idx)해준다. 
   그 결과, idx노드와 그 자손들의 heap배열이 채워진다.
6. heap배열을 순회하며 값을 출력해준다. 끝!

<dfs함수>
: k의 자손들의 heap배열 채우기

1. downnum을 증가시키면서 heap[idx]=downnum 해준다.
   downnum>n이면 min-heap을 만들지 못한다는 뜻이므로 -1을 출력하고 종료한다.
2. 왼쪽, 오른쪽 자식노드가 리프노드가 아니면 자식노드도 dfs 해준다.

<insert함수>
: k의 조상, 자손을 제외한 나머지 heap배열 채우기

1. heapnum을 증가시키면서 heap배열을 heapnum으로 채워준다.
   upnum<=heapnum<=downnum이면 (k의 조상, 자손을 채울때 사용한 숫자이면) heapnum=downnm+1해준다.
2. upheap(idx) 함수를 통해 필요시 flip을 해준다.
3. 왼쪽, 오른쪽 자식노드가 리프노드가 아니면 자식노드도 insert 해준다.

<upheap함수>
: insert한 노드 값이 부모노드 값보다 작을때 filp해주기

1. 부모노드와 비교해서 filp이 필요한 상황이라면 min-heap을 만족할때까지 부모노드로 올라가며 flip해준다.

 

 

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int heap[200001]; //1-based -> 부모 idx 를 i 라고 하면 자식은 2i 와 2i+1 이다.
int n,k,p; //노드 수, heap[p]에 k가 와야한다.
int upnum, downnum; //k의 조상노드의 숫자 중 min, k의 자손 노드의 숫자 중 max
int heapnum=0; //heap에 넣어줄 숫자

void dfs(int idx){ //k의 자손 채우기
    downnum++;
    if(downnum>n){ //예외처리
        cout<<-1;
        exit(0);
    }
    heap[idx]=downnum;
    if(idx*2 <=n) dfs(idx*2);
    if(idx*2+1 <= n) dfs(idx*2+1);
}
void upheap(int idx){ //flip처리
    while(idx>1){
        if(heap[idx]<heap[idx/2]) swap(heap[idx], heap[idx/2]);
        idx/=2;
    }
}
void insert(int idx){ //k의 조상,자손 말고 나머지 채우기
    heapnum++;
    if(heapnum==upnum) heapnum=downnum+1;
    heap[idx]=heapnum;
    upheap(idx); //조상에 나보다 더 큰 수 있으면 flip해주기
    if(idx*2 <=n) insert(idx*2);
    if(idx*2+1 <=n) insert(idx*2+1);
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin>>n>>k>>p;

    // k 있는곳의 부모, 자식 채우고, 사용한 숫자의 최솟값upnum 최댓값downnum 저장
    downnum=k-1;
    dfs(p); // heap[p]=k; 자손 채우기
    upnum=k;
    while(p/2>0){ // k의 조상 채우기
        p/=2, upnum--;
        heap[p]=upnum;
    }
    if(upnum<=0){ //예외처리
        cout<<-1;
        return 0;
    }

    // 배열순회하면서 안채워진곳(0인곳)을 1부터 heapnum++하며 채워준다.
    // 근데 그수가 upnum~downnum이면 다른수로. 그리고 필요시 flip처리
    for(int i=1; i<=n; i++){
        if(heap[i]) continue; //이미 채워져있으면 패스(k의 조상or자손인 경우)
        insert(i); //heap[i]와 그 노드의 자손들을 다 채워오자
    }

    //출력
    for(int i=1; i<=n; i++) cout<<heap[i]<<'\n';
    return 0;
}