- 1. Problem
- 2. My Approach
- 3. Implementation
- 4. Textbook Approach
- 5. Implementation
- 6. Analysis
- 7. Feedback
1. Problem
2. My Approach
- 전시관들은 사이클이 없는 그래프로 존재한다.
- 위 그래프는 root 노드가 없는 트리 모양을 하고 있다. (즉 모든 노드가 root 노드가 될 수 있다)
- leaf 노드부터 시작하면, leaf 노드의 부모노드부터 카메라가 설치되면서 상위 노드로 진행한다.
- 특정 노드에 카메라가 설치되면 해당 노드의 자식 노드와 호출한 부모노드를 비롯한 인접 노드들의 상태가 바뀐다.
3. Implementation
//
// main.cpp
// Gallery
//
// Created by Heejun Lee on 7/22/17.
// Copyright © 2017 Heejun Lee. All rights reserved.
//
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;
int T, V, E;
bool visited[1000], camera[1000];
vector<int> edge[1000];
//DFS
bool check(int here){
visited[here] = true;
// 단일 갤러리
if(edge[here].size()==false) return false;
bool watched = false;
for(int there=0;there<edge[here].size();there++){
int child = edge[here][there];
if(!visited[child])
if(!check(child)){
camera[here] = true;
watched = true;
}else
if(camera[child])
watched=true;
}
return watched;
}
int install(){
for(int i=0;i<V;i++)
if(!visited[i])
if(!check(i))
camera[i]=true;
int count=0;
for(int i=0;i<V;i++)
if(camera[i])
count++;
return count;
}
int main() {
cin >> T;
while(T--){
memset(visited, 0, sizeof(visited));
memset(camera, 0, sizeof(camera));
cin >> V >> E;
for(int i=0;i<E;i++){
int a,b;
cin >> a >> b;
edge[a].push_back(b);
edge[b].push_back(a);
}
cout << install() << endl;
for(int i=0;i<V;i++)
edge[i].clear();
}
return 0;
}
- 임의의 노드에서
dfs로 접근하는check( )함수는 현재 노드의 자식 노드로 접근한다. check(int here)은here의 감시상태를 반환한다.check(int here)은 leaf 노드까지 접근하여visited와watched값을 갱신한 뒤 해당 leaf 노드로 접근하게 한 재귀함수가 반환(감시상태)하여 상황에 따라 here에 카메라를 설치하거나(child가 감시상태 아닌경우)watched값만을 갱신한다(child에 카메라가 있는 경우).install( )함수에서 모든 노드에dfs를 적용하여 카메라 설치를 한다- 인접한 노드의 경우 dfs로 leaf노드까지 접근하여 돌아오면서 업데이트되고 최종 부모노드의 상황에 따라 카메라를 설치한다.
- 단일 노드인 경우 바로 설치한다.
4. Textbook Approach
- 루트 없는 트리에서 문제 풀기
- 루트 없는 트리를 다루는 가장 기본적인 방법은 임의의 시작점으로부터 깊이 우선 탐색을 수행하는 것이다.
- 결과적으로 얻은 깊이 탐색 스패닝 트리(spanning tree)는 원래 그래프의 구조를 갖고 있으면서, 부모 자식 관계를 갖는 일반적인 트리가 된다.
- 트리의 지배 집합 찾기
- 지배 집합(dominating set) : 각 정점이 자기 자신과 모든 인접한 정점들을 지배한다고 할 때, 그래프의 모든 정점을 지배하는 정점의 부분집합.
- 트리의 최소 지배 집합을 찾는 가장 간단한 방법은 트리의 맨 아래에서부터 시작해서 위로 올라가는 것이다.
- 잎 노드는 선택하지 않는다.
- 이 외의 노드에 대해, 트리의 맨 밑에서부터 올라오면서 다음과 같이 선택 여부를 결정한다.
a) 자기 자손 중 아직 지배당하지 않은 노드가 하나라도 있다면 현재 노드를 선택
b) 이 외의 경우 현재 노드를 선택하지 않음
5. Implementation
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
vector<int> a[1001];
bool check[1001];
int installed;
const int WATCHED = 0;
const int UNWATCHED = 1;
const int INSTALLED = 2;
int dfs(int node) {
check[node] = true;
bool children[3] = {};
for (int i = 0; i<a[node].size(); i++) {
int next = a[node][i];
if (check[next] == false) {
children[dfs(next)] = true;
}
}
if (children[UNWATCHED])
{
installed++;
return INSTALLED;
}
if (children[INSTALLED])
return WATCHED;
return UNWATCHED;
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int g, h;
scanf("%d %d", &g, &h);
memset(a, 0, sizeof(a));
memset(check, false, sizeof(check));
for (int i = 0; i < h; i++)
{
int u, v;
scanf("%d %d", &u, &v);
a[u].push_back(v);
a[v].push_back(u);
}
installed = 0;
for (int i = 0; i < g; i++)
if (!check[i] && dfs(i) == UNWATCHED)
installed++;
printf("%d\n", installed);
}
}
dfs를 통해 leaf 노드까지 접근한뒤 상태(UNWATCHED)를 반환한다.- 이 후 반환되는 children의 상태에 따라 현재 노드의 상태 값을 반환한다
6. Analysis
- 결과적으로 두 코드 모두 그래프에 대한 깊이 우선 탐색 한 번으로 원하는 답을 계산하게 되므로, 두 알고리즘의 시간 복잡도는 O(g+h)가 된다.
7. Feedback
좀 더 다양한 그래프 문제를 풀어보면서 문제를 시각화하고 그 정보를 구현하는 연습을 할 필요성을 절실히 느낀다…