[그래프] GALLERY 감시 카메라 설치

1. 문제

 

모든 방을 감시할 수 있게 감시 카메라를 최소한으로 설치해야한다.

 

이때 방은 모두 트리 간선을 이루고 있다고 한다. (연결되지 않은 방 또한 있다.)

 

 

 

어떤 방에 카메라를 설치했다고 하자.

 

그러면 그 방 주위의 방들을 감시할 수 있다.

 

1칸밖에 감시를 못하므로

 

이것은 '리프' 에서부터 차근 차근 카메라를 설치해야한다.

 

 

 

'리프' 에서부터 탐색하는하는 것은

 

dfs를 이용하면 쉽게 구현할 수 있다.

 

 

 

 

2. dfs 

 

일단 루트에서부터 dfs를 실행하게 되면

 

제일먼저 종료되는 dfs는 '리프'이다.

 

 

'리프' 이전의 방에서는 무조건 카메라가 설치되어야 '리프'를 감시 할 수 있다.

 

그러므로 '리프' 이전의 방에 카메라를 설치한다.

 

 

 

이 문제에서 '리프'는 연결점이 타고내려온 것을 제외하고는 아무것도 없는 정점을 말하나

 

연결된 방들이 전부 감시되고 있지만 자신은 감시되고 있지 않은 방 또한 리프라고 말할 수 있다.

 

 

 

 

그러므로 방문할 수 있는 연결점을 카운트 해야 '리프'를 파악할 수 있다.

 

만약 감시되고 있지 않은 u 에서 v로 갈때 v가 이미 감시되고 있다면 연결점 카운트를 세지 않아야한다.

 

 

 

그리고 만약 '루트' 가 '리프'가 되는 상황이라면 무조건 카메라를 설치한다.

 

 

3. 책 해설: 트리의 지배 집합찾기(dominating set)

그래프의 모든 정점을 지배하는 정점의 부분집합을 그래프의 지배 집합이라고 부른다.

 

주어진 그래프에 특정 크기를 갖는 최소 지배 집합이 있는지 확인하는 문제는 NP-완전 문제중 하나이다

 

이는 가장 좋은 알고리즘도 정점 개수의 지수 함수에 비례하는 시간이 걸린다.

 

 

하지만 이 문제는 루트 없는 트리이다.

 

 

트리의 지배 집합을 찾는 간단한 방법은 트리의 맨 아래에서부터 시작해서 위로 올라오는 것이다.

 

트리의 루트를 선택해야 할지 말아야 할지는 미리 알기 어렵지만

 

잎노드는 자기 자신과 부모밖에 지배하지 못하는 반면,

 

그 부모 노드를 선택해서 손해 볼일은 절대 없고 

 

잎노드는 절대로 선택할 필요가 없다.

 

1. 잎노드는 선택 x

2. 다음과 같이 선택 여부를 결정

- 자기 자손 중 아직 지배 당하지 않은 노드가 하나라도 있다면 현재 노드를 선택.

- 이외의 경우 현재노드를 선택하지 않음

 

dfs는 here를 루트로 하는 서브트리를 방문하고 반환하면서 해당 노드가 지배 집합의 일부로 선택되었는지,

아니면 다른 노드에 지배당하고 있는지, 아니면 지배당하지 않고 있는지를 반환.

 

결과적으로 이 알고리즘의 시간복잡도는 O(g +h)가 된다.

 

 

 

 

 코드는 다음과 같다, 책에서는 더 깔끔하게 구현되어있다,

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
 
using namespace std;
 
int C;
vector< vector<int> > graph;
vector<int> visited;
vector<bool> monitor;
int camera;
 
int dfs(int here, bool isRoot)
{
    int settingCamera = 0, subtree = 0, count = 0, thereMonitor = 0;
    
    visited[here] = true;
 
 
    for(int i = 0 ; i < graph[here].size(); i++)
    {
        if(!visited[graph[here][i]])
        {
            count++;
            subtree = dfs(graph[here][i], false);
            if(monitor[graph[here][i]]&&!monitor[here]) count--;
            if(subtree == 0&&settingCamera == 0)
            {
                monitor[here] = true;
                camera++;
                settingCamera = 1;     
                for(int i = 0 ; i  < graph[here].size(); i++)
                    monitor[graph[here][i]] = true;
            }
        }
    }
 
    if(graph[here].size() == 0 || (isRoot&&!monitor[here]))
    {
        monitor[here] = true;
        camera++;
    }
 
    return count;
}
int dfsAll()
{
    camera  = 0;
    visited = vector<int>(graph.size(), false);
    monitor = vector<bool>(graph.size(), false);
    for(int i = 0; i < graph.size(); i++)
    {
        if(!visited[i])
            dfs(i, true);
    }
    return camera;
}
 
int main()
{
    cin>>C;
    while(C--)
    {
        int G, H;
        cin>>G>>H;
        
        graph = vector<vector<int> >(G, vector<int>(0));
        for(int i = 0; i < H; i++)
        {
            int a, b;
            cin>>a>>b;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        cout<<dfsAll()<<"\n";
    }
}

 

 

 

 

868p

 

 

 

 

GALLERY