반응형
https://www.acmicpc.net/problem/25498
25498번: 핸들 뭘로 하지
효규가 얻을 수 있는 문자열은 사전순으로 "$\text{aa}$", "$\text{aaa}$", "$\text{aaaa}$", "$\text{aaaa}$"이므로 "$\text{aaaa}$"를 핸들로 정한다.
www.acmicpc.net
[ 문제풀이 ]
1. 문자열과 그래프를 입력받고, arr[500001]과 vector<int> list[500001]에 저장합니다.
2. node struct를 만들어 현재 노드의 번호, 인덱스 그리고 부모의 문자를 저장합니다.
3. queue<node> q를 만들어 bfs를 돌면서 해당 인덱스에서 가장 큰 문자를 ans에 더해주면서 문자열을 완성합니다.
4. ans를 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | #include<iostream> #include<vector> #include<queue> #include<string> using namespace std; struct node { int cur, idx; char parent; }; int N; char arr[500001]; vector<int> list[500001]; int visited[500001]; string ans; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> arr; for (int i = 0; i < N - 1; i++) { int u, v; cin >> u >> v; list[u].push_back(v); list[v].push_back(u); } queue<node> q; q.push({ 1, 1, '0'}); visited[1] = 1; ans += '0'; while (!q.empty()) { const int cur = q.front().cur; const int idx = q.front().idx; const char pa = q.front().parent; q.pop(); if (pa != ans[idx - 1]) continue; if (idx >= ans.size()) ans += arr[cur - 1]; else if (ans[idx] < arr[cur - 1]) { ans[idx] = arr[cur - 1]; } for (auto& next : list[cur]) { if (visited[next] != 1) { visited[next] = 1; q.push({ next,idx + 1, arr[cur - 1]}); } } } ans.erase(ans.begin()); cout << ans; } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 5069번 - 미로에 갇힌 상근 (C++) (0) | 2023.10.15 |
|---|---|
| [ 백준 ] 1737번 - Pibonacci (C++) (0) | 2023.10.14 |
| [ 백준 ] 19942번 - 다이어트 (C++) (0) | 2023.10.12 |
| [ 백준 ] 21276번 - 계보 복원가 호석 (C++) (0) | 2023.10.11 |
| [ 백준 ] 17085번 - 십자가 2개 놓기 (C++) (0) | 2023.10.10 |