백준 25498 - 핸들 뭘로 하지 (C++)

문제

• 문제 링크

  
   BOJ 25498 - 핸들 뭘로 하지 
  

• 문제 요약

정점마다 알파벳이 메겨진 트리가 주어진다.
문제의 정의데로 알파벳을 이어 붙일 때, 사전상 가장 마지막에 오는 문자열을 구해보자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$1 ≤ N ≤ 500,000$

알파벳은 소문자만 등장한다.

알고리즘 분류

• 그래프 이론(graphs)
• 그래프 탐색(graph_traversal)
• 너비 우선 탐색(bfs)
• 트리(trees)
• 그리디 알고리즘(greedy)

풀이

$N$이 작았다면 모든 리프 노드에서 답을 갱신해도 됐을 테지만, $N ≤ 500,000$ 이므로 풀이를 개선해야 한다.
다음을 관찰하자.

• 루트에서 임의의 깊이까지 서로 다른 경로를 통해 나열되는 문자열들의 길이는 모두 같다.
• 깊이가 같은 정점들에 대해, 사전상 앞선 알파벳이 메겨진 정점들은 답이 될 수 없다.
• 이에 따라 임의의 깊이에선 사전상 가장 마지막에 오는 문자가 메겨진 정점들만이 답의 후보가 될 수 있다.
• 즉, 답의 후보가 될 수 있는 경로들은 모두 같은 문자들을 타고 리프 노드를 향해 내려간다.

---

위 내용은 $bfs$를 이용하면 쉽게 구현할 수 있다.(물론 $dfs$ 로도 가능)

구체적으로 임의의 깊이를 조사할 때, 이전 깊이에서 추가한 정답 후보군들로만 탐색을 진행하면 된다.

매 시행마다 사전상 가장 마지막에 오는 문자를 찾자.
다음 시행에서 쓰일 정답 후보군들은 바로 이 문자가 메겨진 정점들이다.

큐가 빌 때까지 위 시행을 반복하고, 찾아지는 문자들을 이어 붙여 주면 정답 문자열이 완성된다.
자세한 건 코드를 참조하자.

전체 코드

#include<bits/stdc++.h>
#define N 500001
using namespace std;
 
vector <int> Gr[N];
char C[N];
 
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for (int i(1); i <= n; cin >> C[i++]);
    for (int i, j, o{}; ++o < n;)
        cin >> i >> j, Gr[i].push_back(j), Gr[j].push_back(i);
}
void Solve(string an)
{
    queue <int> Q;
    bool V[N]{ 1, 1 };
    for (Q.push(1); Q.size();)
    {
        queue <int> NQ;
        char ch{};
        for (int i(Q.size()); i--;)
        {
            int t(Q.front()); Q.pop();
            for (int& j : Gr[t])
                if (!V[j] && C[j] >= ch)
                {
                    ch = C[j], V[j] = 1;
                    NQ.push(j);
                }
        }
        if (ch)
            for (an += ch; NQ.size(); NQ.pop())
                if (C[NQ.front()] == ch)
                    Q.push(NQ.front());
    }
    cout << an;
}
int main()
{
    Init();
    Solve(string() + C[1]);
}

comment

끝