Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 최소 공통 영역(Lowest Common Region) 찾기

문제 이해하기

여러 개의 지역(region) 목록이 주어지며, 각 목록의 첫 번째 지역은 해당 목록에 속한 나머지 모든 지역을 포함하는 상위 지역입니다. 즉, 지역 X가 지역 Y를 포함하고 있다면 X는 Y보다 더 넓은(상위의) 지역이고, 정의에 따라 모든 지역은 스스로를 포함합니다.

이러한 구조에서 두 지역 r1과 r2가 주어졌을 때, 두 지역을 모두 포함하는 가장 작은 공통 영역을 찾아야 합니다. 한 지역을 포함하는 상위 지역은 유일하다는 조건이 보장되므로 포함 관계는 트리 형태를 이루며, 정답 역시 항상 하나로 결정됩니다.

예를 들어 입력이 아래와 같고 r1 = 'Quebec', r2 = 'New York'이라면, 두 지역을 모두 포함하는 가장 작은 지역인 'North America'가 출력됩니다.

[["Earth","North America","South America"],
 ["North America","United States","Canada"],
 ["United States","New York","Boston"],
 ["Canada","Ontario","Quebec"],
 ["South America","Brazil"]]
r1 = "Quebec", r2 = "New York"

해결 접근 방법

이 문제는 본질적으로 트리 구조에서 두 노드의 최소 공통 조상(LCA, Lowest Common Ancestor)을 구하는 문제와 같습니다. 각 지역의 부모 정보만 파악하면 되므로, 다음 순서로 간단하게 해결할 수 있습니다.

  1. 각 지역의 부모를 저장할 map(parent)을 생성합니다.
  2. x에서 출발해 부모를 따라 루트까지 올라가며, 거치는 모든 지역을 set(chain)에 기록합니다.
  3. y가 chain에 속할 때까지 y를 부모 방향으로 한 단계씩 이동시킵니다.
  4. chain에 처음으로 도달한 y가 곧 두 지역의 최소 공통 영역이므로 이를 반환합니다.

알고리즘 단계 정리

  • parent라는 이름의 map을 생성합니다.
  • i를 0부터 r의 크기까지 반복합니다.
    • j를 1부터 r[i]의 크기까지 반복하며 parent[r[i][j]] := r[i][0]을 설정합니다.
  • chain이라는 set을 만들고 x를 삽입합니다.
  • x가 parent에 존재하는 동안 x := parent[x]로 갱신하고, x를 chain에 삽입합니다.
  • y가 chain에 존재하지 않는 동안 y := parent[y]로 갱신합니다.
  • y를 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 동작 과정을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string findSmallestRegion(vector<vector<string>>& r, string x, string y) {
      map < string, string> parent;
      for(int i = 0; i < r.size(); i++){
         for(int j = 1; j < r[i].size(); j++){
            parent[r[i][j]] = r[i][0];
         }
      }
      set <string> chain;
      chain.insert(x);
      while(parent.find(x)!=parent.end()){
         x = parent[x];
         chain.insert(x);
      }
      while(chain.find(y)==chain.end()){
         y = parent[y];
      }
      return y;
   }
};
main(){
   vector<vector<string>> v = {
      {"Earth","North America","South America"},
      {"North America","United States","Canada"},
      {"United States","New York","Boston"},  
      {"Canada","Ontario","Quebec"},{"South America","Brazil"}
   };
   Solution ob;
   cout << (ob.findSmallestRegion(v, "Quebec", "New York"));
}

입력 및 출력 확인

입력

[["Earth","North America","South America"],["North America","United States","Canada"],
["United States","New York","Boston"],["Canada","Ontario","Quebec"],["South America","Brazil"]]
"Quebec"
"New York"

출력

North America

시간 및 공간 복잡도

부모 맵을 구성하는 데 전체 지역 수 N에 비례하는 시간이 소요되고, 이후 두 지역을 루트 방향으로 올리는 과정은 트리의 최대 깊이 H에 비례합니다. std::map과 std::set의 연산이 로그 시간을 요구하므로 전체 시간 복잡도는 O(N log N), 공간 복잡도는 O(N)입니다. unordered_map과 unordered_set을 사용하면 평균적으로 더 빠른 처리가 가능합니다.