[11주차_화요일] 정점들의 거리

yeongleej commented 4 days ago

사이트 : 백준(BOJ)
문제: 정점들의 거리
번호: 1761

LCA(최소 공통 조상)을 공부할 수 있는 문제였습니다!

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

KodaHye commented 2 days ago

🤔 시간복잡도 고려사항

정점의 개수: 40,000 (간선의 개수: N - 1)
1 ≤ 노드 쌍 ≤ 10,000
두 노드 사이의 거리를 구하기 위해 다익스트라를 사용한다면 79,999(노드 + 간선) * 10,000(노드쌍)이므로 시간초과
LCA(최소공통조상)를 통해 문제를 풀이한다면 최악의 경우 10,000 * 40,000 (최악의 경우는 4억번 연산을 하는 것이지만, 시간 내에 연산하는 것 같음)
최소공통조상이란?
- 트리에서 임의의 두 노드를 선택했을 때, 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모노드를 탐색했을 때, 처음 공통으로 만나게 되는 부모 노드

💡 풀이 아이디어

트리의 정보를 간선리스트로 입력받음
- Node(int e, int w), ArrayList<Node> adj[] 사용
시작지점을 1로 설정하여 BFS 시작하고, dis, depth, p 값 채우기
- int[] dis: 루트로부터 자기 자신까지의 거리
- int[] depth: 트리에서 자신의 depth 구하기
- int[] p: 자기 자신의 직접적인 부모가 누구인지 저장
long LCA(int a, int b)
- a, b의 최소공통조상 구하고, 두 점 간 사이 거리 구하기
  - (루트 ~ a 까지의 거리) + (루트 ~ b 까지의 거리) - 2 * (루트 ~ 최소공통조상까지의 거리)
- 최소공통조상을 구할 때, a와 b의 depth가 다르다면 depth를 작은걸로 맞춰줘야 됨
  - depth는 항상 a의 depth가 작다고 설정함
  - depth 맞추고 한 칸씩 단계별로 자기 자신을 부모로 값을 바꾸면서, a == b가 될 때까지 반복

한 번 풀어봤던 문제여서 문제 접근 방법을 알고 있었습니다!

baexxbin commented 2 days ago

🤔 시간복잡도 고려사항

정점: 2 ≤ N ≤ 40,000
노드 쌍: 1 ≤ M ≤ 10,000
개선된 LCA(최소공통조상) 이용
- 2^i번째에 대한 부모노드 값 저장
'모든 노드의 깊이 찾기'의 차이
- DFS이용(기본)
  - 매 쿼리마다 부모로 올라가기에 O(NM)
- 2^i승에대한 dp이용
  - 2^i만큼 건너뛰기에 O(MlogN)
  - 대신 공간복잡도가 늘어남

💡 풀이 아이디어

parents[j][i]
- j노드의 2^i번째 부모 값
루트로 부터 모든 노드의 깊이 구하기 (setTree())
- dfs를 통해 루트로부터의 현재 노드x의 깊이 구하기
- 이때 자신의 바로 위 부모 값 parents[nxt.u][0] = x; 설정
2^i에 대한 부모 값 설정(setParents())
- 바로 직전 부모값을 바탕으로 2제곱별 부모값 구하기
- parents[j][i] = parents[parents[j][i - 1]][i - 1];
  - j노드의 2^i번째 값은, j의 2^i의 조상(i-1)의 조상(i-1) 값

LCA 진행(LCA())

a, b의 깊이 동일하기 맞추기
- a값이 깊은 값으로 설정해서 진행
깊이를 맞춘 후 a,b의 부모가 같으면 해당 부모 바로 반환

부모가 다르면 공통 부모 찾기

for (int i = mxDepth - 1; i >= 0; i--) {            // 부모가 다르면 같이 부모찾으러 떠나기
      if (parents[a][i] != parents[b][i]) {
          a = parents[a][i];
          b = parents[b][i];
      }
  }
  return parents[a][0];           // 최종적으로 찾은 부모 값 반환

큰 거리부터 건너뛸 수 있는지 확인하며 부모 찾기

a, b 사이 거리 구하기
- (a에서 루트까지 거리 + b에서 루트까지 거리) - (a,b공통 부모에서 루트까지 거리*2)

LCA... 처음 알게된 개념인데 쉽지 않네요.... 개념 공부하면서 했는데도.. 저 근데 궁금한게 parents에서 최대 부모값 배열 크기를 설정할때, 트리의 최대높이(logN+1)로 설정하는데 편향된 트리일 경우 크기가 더 커야할텐데 왜 그냥 logN+1로 사용하는건지 아시나요....??

KodaHye commented 2 days ago

수빈님 질문에 대해 답변 드리겠습니다! (어디에 답변해야될지 모르겠어서,,, 여기에 올려욤,,) 우선 LCA를 구하는 방법이 크게 두 가지가 있는데, 첫 번째가 일반적인 방법으로 제가 사용한 방법이고, 수빈님이 하신건 질의의 개수가 많을 때 사용하는 개선된 LCA입니다. 개선된 LCA에서 parents 배열의 크기를 (logN + 1)로 설정해야 되는 이유는 이게 단순히 트리의 최대 깊이를 의미하는 것이 아니라, 어떤 지점에 대해 2^k 까지의 부모 노드가 뭔지 저장해야 되기 때문에 그런 것으로 알고 있습니다. 그래서 편향트리가 되더라도 상관없게 되는 것 같습니다!

예시를 2개 그려봤는데요,, 혹시 잘못된거 같은 내용 있음 말해주세요!!

yeahdy commented 2 days ago

🤔 시간복잡도 고려사항

알고리즘: LCA(최소 공통 조상찾기)+DFS
시간복잡도: N(2 ≤ N ≤ 40,000) 트리의 높이 최대 16 (log2^N > log2^40000 은 15.3)

💡 풀이 아이디어

dfs 메소드
- 각 노드별로 이어진 노드를 탐색하면서 정점까지의 거리 누적하여 저장
- 이때 각 노드의 직속 노드를 저장해서 초기화하기 (dp 배열에서 상위 부모를 찾을 때 사용)
dp 메소드
- 각 노드별로 여러 레벨에서의 상위 부모 저장하기
- 전체 트리에 대해 다중 차수의 부모 노드를 미리 계산하여 최소 부모 조상(LCA)을 찾을 때 빠르게 접근하기
```
//전체 트리에서 각 노드별로 다중 차수 부모 노드들 저장
static void saveParents(){
for(int from=1; from<MAX; from++){
    for(int to=1; to<n+1; to++){
        int parent = dp[to][from-1];    //특정노드의 레벨의 부모노드
        dp[to][from] = dp[parent][from-1];
    }
}
}
```
- dp[to][0]: to 노드의 직속 부모
- dp[to][1]: to 노드의 2번째 부모 (직속 부모의 부모)
- dp[to][2]: to 노드의 4번째 부모 (2번째 부모의 부모)
- LCA에서 깊이가 다른 두 노드를 같은 깊이 레벨로 맞출 때 부모 노드를 통해 공통 부모를 갖도록 함
lca 메소드
- 출발노드-도착노드 가 있을 때 둘 중 하나를 더 깊은 노드로 기준점 잡기
  - 항상 기준으로 잡은 노드를 더 깊은 노드로 만들기
- 출발노드-도착노드 가 서로 다른 레벨에 있을 경우 깊이를 맞추기
  - 이때 가장 깊은 노드부터 시작해서 깊은 노드를 현재 레벨로 올리면서 갱신
- 출발노드-도착노드 의 깊이 레벨을 맞추고, 서로 같은 부모를 가지고 있다면 공통 부모노드 반환
- 만약 깊이가 같지만 서로 부모가 다를 경우 가장 깊은 노드부터 같은 부모가 나올 때 까지 계속 이동

정말... 너무..어렵네요... 설명은 이해가 가는데 dp 배열에 메모리제이션 구현 코드 부분이 너무 이해하기 어려웠어요...

yeongleej commented 1 day ago

🤔 시간복잡도 고려사항

N ≤ 40,000
M ≤ 10,000

=> 다익스트라 이용 : N O(N logN) -> 시간초과 => 최소 공통 조상(LCA) : O(N M) -> 가능

💡 풀이 아이디어

기본 최소 공통 조상(LCA)
parent[] : 부모노드 정보
d[]: 각 노드까지의 깊이 정보
c[]: 각 노드까지의 깊이가 계산 여부
1. 모든 노드에 대한 깊이(depth) 계산
  - dfs() 이용
2. 최소 공통 조상을 찾을 두 노드 확인
  - lca(a, b)
  - a와 b 깊이 같게 하기: 먼저 두 노드의 깊이가 동일하도록 거슬러 올라감
  - a와 b 부모 같게하기: 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모방향으로 거슬러 올라감
3. lca(a,b) 연산에 대해 2번 과정 반복

GreatAlgorithm-Study / AlgorithmStudy