일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- dfs
- 가끔은 말로
- 너비 우선 탐색
- 회고록
- 분할 정복
- back propagation
- 2023
- 자바스크립트
- object detection
- 조합론
- 문자열
- lazy propagation
- 우선 순위 큐
- 알고리즘
- c++
- pytorch
- tensorflow
- 세그먼트 트리
- 이분 탐색
- Overfitting
- 백트래킹
- dropout
- 다익스트라
- 가끔은_말로
- 크루스칼
- DP
- BFS
- 미래는_현재와_과거로
- NEXT
- 플로이드 와샬
Archives
- Today
- Total
Doby's Lab
[알고리즘] 백준 5941번: Meeting Place (C++) 본문
https://www.acmicpc.net/problem/5971
5971번: Meeting Place
Bessie and Jonell are great friends. Since Farmer John scrambles where the cows graze every day, they are sometimes quite far from each other and can't talk. The pastures and paths on FJ's farm form a 'tree' structure. Each pasture has exactly one distinct
www.acmicpc.net
영어문제였지만 어느 정도 해석이 가능했기에 풀 수 있었다.
1) 노드의 개수와 쿼리의 개수가 주어진다.
2) 2 ~ n까지 부모 노드가 무엇인지 주어진다.
3) m번 동안 a와 b의 LCA를 찾아라.
시간 복잡도는 O(n * m) = O(1000 * 1000)으로 기본적인 LCA를 돌려서 구할 수 있었다.
다른 점은 애초에 입력에서 parent노드가 주어지기 때문에 tree 전처리를 할 때, 부모 노드는 할당해줄 필요가 없었다.
>> level만 갱신해주었다.
[AC 코드]
#include <iostream>
#include <vector>
#define MAX (1000 + 1)
using namespace std;
int parent[MAX];
int level[MAX];
vector<int> graph[MAX];
int n, m;
void treeSet(int node, int pNode) {
level[node] = level[pNode] + 1;
for (int i = 0; i < graph[node].size(); i++) {
int child = graph[node][i];
//if (child == pNode) continue;
treeSet(child, node);
}
}
void swap(int* a, int* b) {
int* temp = a;
a = b;
b = temp;
}
int lca(int a, int b) {
if (level[a] < level[b]) swap(a, b);
while (level[a] > level[b]) {
a = parent[a];
}
while (a != b) {
a = parent[a];
b = parent[b];
}
return a;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 2; i <= n; i++) {
int v;
cin >> v;
graph[v].push_back(i);
parent[i] = v;
}
treeSet(1, 0);
for (int i = 0, a, b; i < m; i++) {
cin >> a >> b;
cout << lca(a, b) << '\n';
}
return 0;
}
728x90
'PS > BOJ' 카테고리의 다른 글
[자료구조] 백준 6218번: Balanced Lineup (C++) (0) | 2021.12.13 |
---|---|
[자료구조] 백준 12837번: 가계부 (Hard) (C++) (0) | 2021.12.13 |
[알고리즘] 백준 3584번: 가장 가까운 공통 조상 (C++) (0) | 2021.12.13 |
[알고리즘] 백준 11437번: LCA (C++), 최소 공통 조상 (0) | 2021.12.13 |
[자료구조] 백준 16975번: 수열과 쿼리 21 (C++) (0) | 2021.12.12 |