https://www.acmicpc.net/problem/10775 큰 번호의 게이트부터 도킹해야 최대한 많은 비행기를 도킹할 수 있다. 파인드 연산을 통해 이미 도킹했다면 앞의 게이트와 연결 시켜서 다음 도킹할 자리를 빨리 찾을 수 있다. 파인드 연산 결과가 0이라면 더 이상 도킹할 자리가 없으므로 종료 시켜주면 된다. 12345678910111213141516171819#include int n,m,t,c,r,p[100001];int Find(int x) { return x==p[x]?x:p[x]=Find(p[x]); } int main(){ scanf("%d %d",&n,&m); for(int i=1;i
1761 정점들의 거리
https://www.acmicpc.net/problem/1761 트리에서의 두 정점 사이의 경로는 하나만 존재하므로 경로 사이의 거리가 곧 최단 거리가 된다. 이 점을 이용하여 루트에서 부터의 정점 i까지의 거리를 d[i]라 하면 두 정점 u,v 사이의 거리는 d[u]+d[v]에서 경로에 해당되지 않는 부분인 d[lca(u,v)]가 두 번 포함되었으므로 dist(u,v)=d[u]+d[v]-2*d[lca(u,v)] 이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include #include #include using namespace std..
https://www.acmicpc.net/problem/11437 트리에서 두 노드의 LCA (Lowest Common Ancestor), 즉 가장 가까운 공통 조상을 찾는 문제이다. Naive한 방법으로 O(N)만에 구할 수 있다. 모든 노드를 루트에서 시작하여 BFS (Breadth First Search)로 탐색하여 모든 노드의 부모와 깊이를 구한다. 그리고 LCA를 구하고자 하는 두 노드 중 더 깊은 노드를 올려서 두 노드의 깊이를 똑같이 맞춰준다. 그리고 하나씩 동시에 올리면서 처음 두 노드가 같아졌을 때 그 노드가 LCA이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051..