[BOJ/Gold 5] 백준 28270 Marked-Numbered(C++)

문제 링크

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

28270번: Marked-Numbered

 

문제

코치 희승이는 FXC 나라 육상 국가대표 선발 보고서를 작성하였다. 희승이는 보고서를 작성할 때 목차를 육상협회에서 사용하는 글머리 기호 형태로 작성하였다. 희승이가 FXC 나라 문화체육관광부로 공문을 보내려고 봤더니, 문화체육관광부에서는 공문을 작성할 때 글머리 번호 형태로 작성한다. 따라서 희승이는 보고서를 글머리 번호 형태로 바꾼 사본을 만들어서 문화체육관광부로 보내려고 한다.

 

보고서 목차는 위 그림의 트리와 같이 도식화할 수 있다. 트리에서 루트를 제외한 모든 노드는 보고서의 항목과 일대일 대응된다. 트리에서 깊이 우선 탐색(DFS)을 했을 때 방문하는 순서대로 트리 노드에 색인을 매길 수 있는데, 보고서에서 먼저 등장하는 항목이 더 작은 색인을 가진다. 보고서를 글머리 기호 형태로 작성한다면 각 항목의 번호는 항목과 대응하는 노드의 레벨(루트 노드와의 거리)과 같다. 한편 보고서를 글머리 번호 형태로 작성한다면 각 항목의 번호는 항목과 대응하는 노드보다 색인이 작은 형제 노드의 수에 1을 더한 값과 같다.

희승이가 글머리 기호 형태로 작성한 보고서 목차가 주어지면 이를 글머리 번호 형태로 변환하는 프로그램을 작성하여라.

 

입력

첫 번째 줄에 보고서 목차 내 항목의 개수 C가 주어진다.

두 번째 줄에는 글머리 기호 형태로 작성된 보고서에서 i + 1번째(0 ≤ i < C) 항목의 번호 Mi에 해당하는 C개의 정수가 주어진다.

 

출력

만약 주어진 보고서가 올바른 보고서가 아닌 경우 첫 번째 줄에 -1을 출력한다. 보고서가 올바르다면 항목의 번호가 입력과 동일하게 매겨지도록 보고서와 대응되는 트리를 만들 수 있다.

주어진 보고서가 올바른 보고서라면 첫 번째 줄에 C개의 정수 Ni를 출력한다. Ni는 주어진 보고서를 글머리 번호 형태로 바꿨을 때 i + 1번째(0 ≤ i < C) 항목의 번호를 의미한다.

가능한 정답이 여러 가지라면 그중 아무거나 출력한다.

 

서브태스크

모든 데이터에 대해서, 1 ≤ C ≤ 10^6; 1 ≤ Mi ≤ 10^6을 만족한다.

 

번호	배점	제한
1	1	문제에서 주어진 예제만 들어온다.
2	1	Mi ≤ 2
3	1	추가 제약조건은 없다.

 

예제 입력 1

10
1 2 2 2 1 2 3 3 2 2

예제 출력 1

1 1 2 3 2 1 1 2 2 3

예제 입력 2

7
1 2 3 4 3 2 1

예제 출력 2

1 1 1 1 2 2 2

예제 입력 3

5
1 3 5 7 9

예제 출력 3

-1

 

알고리즘 분류

• 자료 구조
• 그래프 탐색

 

풀이

먼저 루트 노드를 만들고 번호를 0으로 매긴다.

그리고 C개의 번호를 입력받는데, 트리를 구성할 수 있는지를 따지는 Answer 변수를 선언하고 true로 초기화한다. 그리고 다음과 같은 경우를 따져서 트리를 구성한다.

• i번째 번호가 현재 노드의 번호보다 1만큼 크다면 현재 노드에 해당하는 항목의 자식 항목이라는 뜻이므로 현재 노드의 자식 노드를 하나 생성하고 번호를 입력받은 번호로 매긴다.
• i번째 번호가 현재 노드의 번호보다 2만큼 크다면 현재 항목의 자식 항목의 자식 항목이라는 뜻이므로, 노드를 자식 노드로 바꾸고 자식 노드를 하나 생성하고 번호를 입력받은 번호로 매긴다.
  • 다만 현재 노드의 자식 노드가 없다면 입력이 잘못되었다는 뜻이므로, Answer 변수를 false로 초기화한다.

• i번째 번호가 현재 노드의 번호 이하라면 현재 항목의 모든 자식 항목은 이제 전부 탐색했고, 새로운 항목이 나타났다는 뜻이므로 그 새로운 항목의 번호보다 1만큼 작은 번호를 가진 노드까지 올라간 후 자식 노드를 하나 생성하고 번호를 입력받은 번호로 매긴다.
• i번째 번호가 위 3가지에 해당하지 않는다면 입력이 잘못되었다는 뜻이므로, Answer 변수를 false로 초기화한다.
• Answer 변수가 false라면 트리 구성을 중단하고 나머지 입력만 받는다.

 

Answer가 true라면 DFS를 활용하여 글머리 번호를 출력한다. false라면 -1을 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct NODE {
    int Index;
    NODE* Prev;
    vector<NODE*> Next;

    NODE(int Number, NODE* Node) {
        Index = Number;
        Prev = Node;
    }

    void insert(int Number) {
        NODE* NowNode = this;
        NowNode->Next.push_back(new NODE(Number, NowNode));
    }
};

int C, M;
bool Answer = true;

void DFS(NODE* NowNode, int Number) {
    // cout << NowNode->Index << " Next Count: " << (int)NowNode->Next.size() << "\n";
    for (int i = 0; i < (int)NowNode->Next.size(); i++) {
        cout << Number++ << " ";
        DFS(NowNode->Next[i], 1);
    }
}

void find_Answer(NODE* Root) {
    if (Answer) {
        DFS(Root, 1);
    }
    else {
        cout << "-1";
    }
    cout << "\n";
}

void input() {
    NODE* Root = new NODE(0, nullptr);
    cin >> C;
    for (int i = 0; i < C; i++) {
        cin >> M;
        if (Answer) {
            if (Root->Index == M - 1) {
                Root->insert(M);
            }
            else if (Root->Index == M - 2) {
                if (Root->Next.empty()) {
                    Answer = false;
                }
                else {
                    Root = Root->Next.back();
                    Root->insert(M);
                }
            }
            else if (Root->Index >= M) {
                int Sub = Root->Index - M + 1;
                while (Sub--) {
                    Root = Root->Prev;
                };
                Root->insert(M);
            }
            else {
                Answer = false;
            }
        }
    }
    while (1) {
        if (Root->Index == 0) {
            break;
        }
        Root = Root->Prev;
    };
    find_Answer(Root);
}

int main() {
    FASTIO
    input();

    return 0;
}