C++ 백준 20955 민서의 응급 수술

백준 20955

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

20955번: 민서의 응급 수술

풀이 전 나의 생각

뉴런과 시냅스가 주어질 때 모든 뉴런이 트리 구조가 될 때 까지의

연산 횟수를 구해야 한다.

 

조건

• 2 ≤ N ≤ 100,000
• 1 ≤ M ≤ min(N × (N – 1) / 2, 100,000)
• 1 ≤ u, v ≤ N
• u ≠ v
• 두 뉴런 사이에는 최대 1개의 시냅스만 존재한다.

과정

문제를 보면 뉴런은 노드고, 시냅스는 간선이라는 것을 알 수 있다.

 

이 문제의 중요점은 연결해주는 연산을 구하는 것이 아닌

연결되있는 노드의 형태가 몇개 있는지 알아내야 한다.

 

이유는 예를 들어, (1, 2)와 (3, 4)의 시냅스 정보가 있다고 가정할 때

2와 3을 어떻게 연결하는지 고민하는것 보다 (1, 2)와 (3, 4) 의 연결 노드 형태의 개수 N을 구해주면

연결해줘야 할 연산의 수는 N - 1의 식으로 쉽게 구할 수 있다.

 

다음으로 사이클이 되는 부분의 연결을 끊어줘야 한다.

왜냐하면 문제에서 구하고자 하는 것은 모든 뉴런을 트리로 만드는 것이기 때문에

사이클이 되는 부분은 모두 제거해줘야 한다.

 

참고로, 사이클의 개수는 사이클을 제거해야 하는 연산 횟수를 의미한다.

 

그럼 최종적으로 연결 노드 형태의 개수 - 1 + 사이클의 개수를 해주면

구해야 하는 연산 횟수를 구할 수 있다.

 

1. 시냅스 정보를 모두 저장한다.

for (int i = 0; i < M; i++)
	{
		int u, v;
		cin >> u >> v;

		link[u].push_back(v);
		link[v].push_back(u);
	}

 

2. 인접한 노드를 모두 탐색했다면, 연결 노드 형태의 개수를 증가시켜준다.

for (int i = 1; i <= N; i++)
	{
		if (!visited[i])
		{
			dfs(i, 0);
			ans++;
		}
	}

dfs를 완료했다는 것은 연결 노드 형태가 하나 완성됐다는 것을 의미하기 때문이다.

 

3. 탐색을 진행하며, 사이클을 탐지해준다.

void dfs(int st, int prev)
{
	visited[st] = true;

	for (int i : link[st])
	{
		if (!visited[i])
		{
			dfs(i, st);
		}
		else if (!cycle[i] && prev != i)
		{
			cycle_cnt++;
		}
	}

	cycle[st] = true;
}

만약, 이전의 노드값이 현재 탐색하고 있는 인접 노드의 값과 다르다면

사이클이 된다는 것을 의미한다. 

 

이유는 이전의 노드값과 인접 노드 값이 같다면 부모 노드와 자식 노드가 서로 바라보고 있다는 것을

의미하고(ex (1, 2) (2, 1)) 반대라면 다른 부모를 바라보고 있기 때문에 사이클이 형성된다.

 

추가적으로, cycle[st] = true까지 도착했다는 의미는 인접 노드의 끝까지 탐색을 완료했다는 의미고

이 과정까지 오기 전에 사이클의 존재를 확인하는 것이다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

vector<vector<int>> link (100001);
bool visited[100001];
bool cycle[100001];
int cycle_cnt = 0;

void dfs(int st, int prev)
{
	visited[st] = true;

	for (int i : link[st])
	{
		if (!visited[i])
		{
			dfs(i, st);
		}
		else if (!cycle[i] && prev != i)
		{
			cycle_cnt++;
		}
	}

	cycle[st] = true;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, M, ans = 0;
	cin >> N >> M;

	for (int i = 0; i < M; i++)
	{
		int u, v;
		cin >> u >> v;

		link[u].push_back(v);
		link[v].push_back(u);
	}

	for (int i = 1; i <= N; i++)
	{
		if (!visited[i])
		{
			dfs(i, 0);
			ans++;
		}
	}

	cout << (ans - 1) + cycle_cnt;
}