[백준 / BOJ] 20955 민서의 응급 수술

문제

출처 : https://www.acmicpc.net/problem/20955

20955번: 민서의 응급 수술

N개의 뉴런(노드) 와 M개의 시냅스(간선)가 주어진다. 이때, M개의 시냅스를 적절히 끊거나 연결해서 N개의 뉴런을 하나의 '트리'구조로 만들려고한다. 끊거나 연결하는 연산횟수를 구하는 문제다.

---

풀이

트리의 정의인 '트리는 항상 N-1개의 간선으로 연결된다'를 이용하면 쉽게 풀리는 문제다.

문제 입력의 노드가 항상 전부 연결된상태로 주어지는것이 아니기 때문에, 우선 연결된 그래프들을 모두 찾은뒤, 해당 그래프 집합들을 각각 트리구조로 만드는데 필요한 연산의 횟수를 구하고 연결시켜줘야한다.

알고리즘은 아래와 같다.

 

1. 그래프집합을 모두 찾으며, 해당 집합에 들어있는 노드의 갯수와 간선의 갯수를 구한다.

 

2. 1번에서 찾은 집합에 들어있는 노드는 항상 모두 연결되어있으므로 집합에 포함된 간선의 수는 항상 (노드의 갯수 - 1)보다 크거나 같음이 보장된다. 이 집합은 트리일수도 그래프일수도 있기때문에, 이 집합을 트리로 만드는데 필요한 연산의 횟수를 구해줘야한다. 하나의 그래프를 트리 형태로 만드는데 필요한 간선의 수는 항상 (노드의 갯수 - 1)이니

(집합에 포함된 간선의 수) - (노드의 갯수 - 1)연산을 진행하면 해당 집합을 트리 형태로 만드는데 필요한 연산의 횟수가 나온다.

 

3. 1,2번을 반복하며 모든 집합을 각각 트리 형태로 만든 후, 서로 연결해 최종 연산횟수를 구한다.

 

문제를 풀때 주의할 점이 있었는데, 노드의 갯수가 최대 100,000이라서, 이미 방문한 경로를 체크해줄때 (2차원)배열을 사용하면 메모리 초과가 나온다. 나 같은 경우는 객체에 equals와 hashCode를 재정의하고 HashSet을 이용해 경로 체크를 해줬다.

 

주요 소스코드

	private int getTreeMakeOpreationCount(){
		boolean[] isUnion = new boolean[this.neurons+1];
		Set<PathKey> isPassed = new HashSet<PathKey>();
		int operationCount = 0;
		int remainSynapseCount = 0;
		int[] result = new int[2];
		for(int i = 1; i <= this.neurons; i++){
			if(isUnion[i]) continue;
			result[0] = result[1] = 0;
			this.countNeuronAndSynapse(i, isUnion, isPassed, result);
			operationCount += this.deleteSynapseCount(result);
			remainSynapseCount += (result[0]-1);
		}
		return operationCount + this.connectSynapseCount(remainSynapseCount);
	}
	
	private void countNeuronAndSynapse(int from, boolean[] isUnion, Set<PathKey> isPassed, int[] result){
		if(isUnion[from]) return; 
		result[0]++;
		isUnion[from] = true;
		for(int i = 0; i < this.graph.get(from).size(); i++){
			int to = this.graph.get(from).get(i);
			if(isPassed.contains(PathKey.instance(from, to))) continue;
			isPassed.add(PathKey.instance(from, to));
			isPassed.add(PathKey.instance(to, from));
			result[1]++;
			this.countNeuronAndSynapse(to, isUnion, isPassed, result);
		}
	}

---

전체 소스 코드

https://github.com/devxb/JJUNalgo/blob/master/20955%20%EB%AF%BC%EC%84%9C%EC%9D%98%20%EC%9D%91%EA%B8%89%20%EC%88%98%EC%88%A0/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃