[알고스팟] GALLERY - 감시 카메라 설치 (C++, 트리의 최소 지배 집합)

문제

 

algospot.com/judge/problem/read/GALLERY

algospot.com :: GALLERY

 

풀이

 

종만북 난이도: 중

 

이번 문제를 해결하는 힌트는 문제 속에 있다.

미술관은 한 번 관람한 갤러리를 다시 가기 위해서는 이전에 지나왔던 복도를 반드시 한 번 지나야 하는 구조로 설계되어 있으며, 모든 갤러리가 서로 연결되어 있지 않을 수도 있습니다.

 

방문한 갤러리(노드)를 다시 가기 위해서는 지나왔던 복도(간선)를 지나야 한다는 것은 미술관 구조(그래프 구조)에 사이클이 존재하지 않는다는 것이다. 이러한 그래프는 결국 루트 없는 트리(unrooted tree)로 나타낼 수 있다.

 

그래프가 루트 없는 트리(unrooted tree)인지 확인하는 3가지 속성은 다음과 같다.

 

1. 간선이 노드의 개수(n) -1 만큼 존재한다.

2. 사이클이 존재하지 않는다.

3. 두 정점을 연결하는 단순 경로는 단 한 개만 존재한다.

 

위의 3가지 속성은 모두 동치이다.

 

그래프를 이처럼 루트 없는 트리로 나타낸다면 더 간단히 문제를 해결할 수 있다.

이전에 풀었던 트리의 지름 구하기나 그래프의 SCC를 하나의 노드로 간주하여 루트 없는 트리로 만드는 축구 전술 문제가 그러하다.

 

 

이번 문제는 지배 집합(dominating set)을 찾는 문제이다. 

지배 집합이란 그래프의 모든 정점을 지배하는 정점의 부분 집합을 의미한다.

하지만 그래프에서 지배 집합을 찾는 알고리즘은 NP-완전 문제로 지수로 증가하는 시간 복잡도를 가지기 때문에 사실상 그래프의 지배 집합으로 해결하긴 힘들다.

따라서 미술관을 루트 없는 트리로 바꾸어 생각해보자.

 

갤러리는 루트 없는 트리로 표현되기 때문에 어떤 노드든 루트로 설정하여 DFS를 진행하여 만들어지는 스패닝 트리를 생각해보자.

감시 카메라는 설치된 갤러리와 그 갤러리와 연결된 갤러리들을 감시할 수 있다. 

따라서 갤러리를 트리의 노드로 표현하면 해당 노드에 카메라를 설치 시 부모 노드와 자식 노드들을 감시할 수 있다.

이제 주변 노드를 모두 지배(감시)할 수 있는 노드의 최소 개수인, 트리의 최소 지배 집합을 구하면 된다.

 

트리의 최소 지배 집합을 구하려면 리프 노드는 카메라를 설치하는 갤러리로 선택해서는 안된다.

그 이유는 리프 노드 대신 그 부모 노드를 선택하면 리프 노드까지 감시할 수 있기 때문이다.

즉, 부모 노드에 설치하여 감시되는 것이 항상 손해가 없다.

따라서 트리의 가장 하위의 노드부터 올라오면서 선택을 하자.

 

 

해당 노드를 카메라를 설치하는 갤러리로 선택하는지 판단하는 조건은 다음과 같다.

 

1. 감시되지 않는 자식 노드가 있는 경우 (UNWATCHED_CHILD = 3)

이번 갤러리에 카메라를 설치해야 자식 노드를 감시할 수 있다.

이번 노드에 카메라를 설치하면 부모 노드는 자동으로 감시된다.

-> 부모 노드는 2번 case(WATCHED_BY_CHILd=2)가 된다.

 

2. 자식 노드에 카메라가 설치되는 경우 (WATCHED_BY_CHILd = 2)

이 경우는 자식 노드가 해당 노드를 감시하기 한다. 

단, 이번 노드의 부모 노드도 자신의 부모 노드에 의해 감시되는 것이 항상 최소 카메라 개수를 유지하는 방법이다.

부모 노드는 3번 case(ONLY_CHILD_WATCHED = 1)가 된다.

 

3. 자식 노드만 감시되는 경우 (ONLY_CHILD_WATCHED = 1)

자식 노드가 자신의 자식 노드에 의해 감시되는 경우이다. 

이번 노드는 자신의 부모의해 감시되는 것이 손해가 없으므로 부모 노드를 선택하도록 하자.

-> 부모 노드는 1번 case(UNWATCHED_CHILD = 3)가 된다.

 

각각의 경우를 상수화한 변수 (UNWATCHED_CHILD, WATCHED_BY_CHILd, ONLY_CHILD_WATCHED)로 나타낸다.

이때 각 경우들에서 우선순위가 높은 순서는 1번->2번 -> 3번 순이다.

 

1번의 경우 이번 노드에 반드시 카메라를 설치해야 한다.

이는 어떠한 노드의 상태보다 가장 우선시 되어야한다.

 

2번의 경우 자식 노드에 의해 이미 이번 노드가 감시되고 있다.

따라서 자식 노드 중에서 감시되지 않는 노드가 있지 않는 이상 이번 노드를 선택할 필요가 없다.

또한 부모 노드에 의해 이번 노드가 감시될 필요는 없다.

즉, 최소 지배 집합을 구하기 위해서는 부모 노드는 선택되서는 안 되므로 ONLY_CHILD_WATCHED가 반환되어야 한다.

 

3번의 경우 자식 노드만 감시된다. 

이 경우는 1,2번 경우와 달리 이번 노드는 카메라를 달거나(선택하거나), 이미 감시되는 경우가 아니다.

따라서 이번 노드의 상태를 전혀 나타내지 않는 정보이기 때문에 가장 우선순위가 낮다.

 

이제 우선순위가 높은 경우에 더 큰 값을 부여하여 자식 노드의 상태 반환 값 중 가장 큰 값이 이번 노드의 상태를 나타낸다.

 

 

int InstallCameraDFS(int now_gallery){
  visited[now_gallery] = true;
 
  int next_gallery, watched_state =0;
  for(int i=0; i<adj[now_gallery].size() ; ++i){
    next_gallery = adj[now_gallery][i];
    if(!visited[next_gallery])
      watched_state = max(watched_state, InstallCameraDFS(next_gallery));
  }
 
  if(watched_state == UNWATCHED_CHILD){ //감시되지 않는 자식 노드가 있는 경우 이번 갤러리에 설치
    ++camera_cnt;
    return WATCHED_BY_CHILd;
  }else if(watched_state == WATCHED_BY_CHILd){  //자식 노드가 이번 갤러리를 감시하는 경우 이번 갤러리의 부모도 설치할 필요는 없음.
    return ONLY_CHILD_WATCHED; 
  }else if(watched_state == ONLY_CHILD_WATCHED){  //자식 노드만 감시되는 경우 이번 갤러리의 부모에 설치.
    return UNWATCHED_CHILD;
  }else{  //watched_state == 0, 리프 노드는 설치하지 않아 감시되지 않음
    return UNWATCHED_CHILD;
  }
 
}

 

 

 

참고 서적: 알고리즘 문제 해결 전략(김종만 저)

 

코드