[문제] 감시 카메라 설치 (GALLERY)

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • GALLERY
  • 1000ms
  • 65536kb
  • 1403
  • 364 (25%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

전세계의 유명한 인물화들을 모아 두는 미술관에 괴도 콩의 도전장이 날아들었습니다. 2022년 2월 2일을 기념하여, 미술관에 전시된 인물화 중 하나의 얼굴을 모 프로게이머의 얼굴로 합성하겠다는 것입니다. 미술관의 관장을 맡고 있는 재하는 이와 같은 사태를 방지하기 위해 감시 카메라를 설치하기로 마음먹었습니다. 미술관은 여러 개의 갤러리와 이들을 연결하는 복도로 구성되어 있으며, 한 갤러리에 감시 카메라를 설치하면 이 갤러리와, 복도로 직접 연결된 갤러리들을 감시할 수 있습니다. 모든 갤러리를 감시하기 위해 필요한 최소 감시 카메라의 수는 몇 개일까요?

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

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 미술관에 포함된 갤러리의 수 G (1 <= G <= 1000) 와 갤러리들을 연결하는 복도의 수 H (0 <= H < G) 가 주어집니다. 각 갤러리에는 0번부터 G-1 번까지의 고유 번호가 있습니다. 그 후 H 줄에 각 2개의 정수로 각 복도가 연결하는 두 갤러리의 번호가 주어집니다.

출력

각 테스트 케이스마다 한 줄에 필요한 카메라의 최소 개수를 출력합니다.

예제 입력

3
6 5
0 1
1 2
1 3
2 5
0 4
4 2
0 1
2 3
1000 1
0 1

예제 출력

3
2
999

SOURCE

package apss;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Gallery {
	
	// 노드 수
	static int G;
	// 간선 수
	static int H;
	// 인접리스트
	static ArrayList<Integer>[] adjList;
	// 발견 순서 저장 (DFS 스패닝 트리)
	static int[] discovered;
	static int count;
	static int installed;
	static final int UNWATCHED = 0;
	static final int WATCHED = 1;
	static final int INSTALLED = 2;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		System.setIn(new FileInputStream("D:\\sample_input.txt"));
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine().trim());
		
		for(int tc=1; tc<=T; tc++){
			StringTokenizer st = new StringTokenizer(br.readLine());
			G = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());
			
			adjList = new ArrayList[G];
			discovered = new int[G];
			
			for(int i=0; i<G; i++){
				adjList[i] = new ArrayList<Integer>();
			}
			
			for(int i=0; i<H; i++){
				
				st = new StringTokenizer(br.readLine());
				int sv = Integer.parseInt(st.nextToken());
				int ev = Integer.parseInt(st.nextToken());
				
				adjList[sv].add(ev);
				adjList[ev].add(sv);
				
			}
			
			count = 1;
			dfsAll();
			
			bw.write(installed + "\n");
			bw.flush();
			
		}
		
		bw.close();

	}
	
	
	public static void dfsAll(){
		installed = 0;
		for(int i=0; i<G; i++){
			if(discovered[i] == 0 && dfs(i) == UNWATCHED){
				++installed;
			}
			
		}
		
	}
	
	public static int dfs(int here){
		
		discovered[here] = count++;
		int[] children = {0,0,0};
		
		for(int i=0; i<adjList[here].size(); i++){
			int there = adjList[here].get(i);
				if(discovered[there] == 0){
					++children[dfs(there)];
				}
		}
		
		// 자손 노드 중 감시되지 않는 노드가 있을 경우 카메라를 설치한다.
		if(children[UNWATCHED] > 0){
			++installed;
			return INSTALLED;
		}
		
		// 자손 노드 중 카메라가 설치된 노드가 있을 경우 설치할 필요가 없다.
		if(children[INSTALLED] > 0){
			return WATCHED;
		}
		
		return UNWATCHED;
		
	}

}

풀이

각 정점이 자기 자신과 모든 인접한 정점들을 지배한다고 할 때, 그래프의 모든 정점을 지배하는 정점의 부분집합을 그래프의 지배 집합(dominating set)이라고 부른다.

 

문제의 힌트는 ' 미술관에서 한 번 지나간 갤러리를 다시 지나기 위해서 전에 지난 복도를 반드시 지나야 합니다' 에 있다. 이 속성의 의미는 미술관을 표현하는 그래프에는 사이클이 존재하지 않는다는 것이다. 그래프에 사이클이 있을 경우, 어떤 복도도 두 번 지나지 않고 두 갤러리를 왕복할 수 있기 때문이다.

사이클이 존재하지 않는 그래프는 노드 간의 상하 관계가 없을 뿐이지 트리와 같은 형태를 가지고 있다. 이와 같은 그래프들을 루트 없는 트리(unrooted tree) 라고 부른다. 어떤 연결된 그래프가 루트 없는 트리인지 확인하려면, 다음 속성 중 하나라도 성립하는지를 확인하면 된다.

 

• 정확히 V-1개의 간선이 있다.
• 사이클이 존재하지 않는다.
• 두 정점 사이를 연결하는 단순 경로가 정확히 하나 있다.

 

이 조건들은 모두 동치로, 한 조건이라도 성립할 경우 다른 조건들이 모두 성립하게 된다.

 

이 문제에서는 모든 갤러리가 서로 연결되어 있을 필요가 없다고 명시되어 있기 때문에, 그래프의 각 컴포넌트가 트리 형태임을 알 수 있다. 각 컴포넌트를 독립적으로 풀어도 된다는 것은 자명하므로, 이제 트리의 최소 지배 집합을 찾는 문제를 풀면 된다.

 

트리의 최소 지배 집합을 찾는 가장 간단한 방법은 트리의 맨 아래에서부터 시작해서 위로 올라오는 것이다. 트리의 루트를 선택해야 할지 말아야 할지는 미리 알기 쉽지 않은 반면, 트리의 잎 노드를 선택할지 말지를 정하기란 아주 쉽다. 잎 노드는 자기 자신과 부모밖에 지배하지 못하는 반면, 부모 노드는 그 외의 노드들도 지배할 수 있다. 따라서 잎 노드 대신 그 부모 노드를 선택해서 손해 볼 일은 절대로 없고, 잎 노드는 절대로 선택할 필요가 없다. 대신 그 부모 노드 모조리 선택해야 한다. 이런 식으로 트리의 맨 밑에서부터 올라가면서 각 노드의 선택 여부를 결정하는 알고리즘을 다음과 같이 설계할 수 있다.

 

1. 잎 노드는 선택하지 않는다.
2. 이 외의 노드에 대해, 트리의 맨 밑에서부터 올라오면서 다음과 같이 선택 여부를 결정한다.
1. 자기 자손 중 아직 지배당하지 않은 노드가 하나라도 있다면 현재 노드를 선택한다.
2. 이 외의 경우 현재 노드를 선택하지 않는다.

 

위 알고리즘의 시간 복잡도는 O(g+h)이다.

* discovered는 스패닝 트리를 만들기 위함인데, 이미 문제에서 트리임을 명시하고 있으므로 굳이 위의 소스처럼 사용할 필요는 없음.

#DFS #DFS 스패닝 트리