백준 1119: 그래프

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

 

이 문제는 보자마자 숨이 턱 막혔었다.

도대체 어떻게 풀어야할지 감이 전혀 잡히지 않았다.

분리 집합을 사용하려해도, 분리집합에선 집합 연결을 끊는 것까지 배우지 않아서, 이 방법은 폐기했고, DFS로 순회하며 BruteForce를 사용하려 해도, 구현이 힘들것 같았기에 다른 방법을 찾아야만 했다.

 

그렇기에, 일단 나는 처음으로 돌아가보도록 했다. 방법을 구하는 게 아니라, 도로를 수정할 경우 합쳐지는 경우가 어떤것인지 생각을 해보았다. 일단 처음 생각한 예제는 다음과 같았다.

점은 도시, 선은 도로를 의미한다.

이 그래프는 아무리 도로를 수정해보아도, 하나로 연결될 수가 없었다. 그러면 여기서 어떻게 도로를 변경했을 때, 하나의 집합으로 만들수 있을까?로 생각을 옮기자, 다른 예제가 떠올랐다.

도로 하나 추가

남는 도로가 있으면 된다는 결론이 내려졌다. 그렇다면, 불필요한 도로만큼 다른 집합과 연결할 수 있다!

 

여기서, 불필요한 도로는 어떻게 구할까? 이를 위해서는 하나의 집합에서 필요한 최소한의 도로를 구하는 것이 필요했다. 만약 N개의 노드들을 전부 연결할 때, 필요한 최소의 도로는? 트리의 선분 갯수, 즉, N - 1개이다.

따라서, DFS로 그래프를 순회할 때, 해당 집합의 도시들의 갯수를 구하면, 자연히 필요한 도로의 갯수를 구할 수 있고, 추가로, DFS로 해당 집합의 도로의 갯수도 구할 수 있다.

 

원래라면, 도로의 갯수와, 도시의 갯수를 각각의 DFS로 따로 구하겠지만, 나는 편의를 위해 리턴값을 pair로 정의해서, 한번에 도로의 갯수와 도시의 갯수를 구했다. 그렇게 나온 코드는 다음과 같다.

#include <iostream>
#include <vector>

using namespace std;
int eCnt = 0, N, G[51][51], gCnt = 0, cnt = 0, num = 0, ans = -1;
char ch;
bool v[2501], visited[51];
pair<int, int> dfs(int here)
{
	pair<int, int> ret = {0, 0};
	for(int i = 0; i < N; i++)
		if (G[here][i] >= 0 && !v[G[here][i]])
		{
			v[G[here][i]] = true;
			bool f = !visited[i];
			visited[i] = true;
			pair<int, int> tmp = dfs(i);
			ret = { ret.first + tmp.first + f, ret.second + tmp.second + 1};
		}
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for(int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
		{
			cin >> ch;
			if (ch == 'Y' && G[j][i] == 0) G[i][j] = ++num;
			else if (G[j][i] > 0) G[i][j] = G[j][i];
			else G[i][j] = -1;
		}
	for(int i = 0; i < N; i++)
		if (!visited[i])
		{
			visited[i] = true;
			pair<int, int> p = dfs(i);
			if (ans >= 0)
				cnt += p.second - p.first - 1;
			else
				cnt += p.second - p.first;
			++ans;
		}
	if (cnt < 0) cout << -1 << '\n';
	else cout << ans << '\n';
}

주의점은 첫 집합은 기존의 집합과 합치는 과정이 아니라서 예외를 두어야한다.

이제 이것이 정답일까? 안타깝게도 아니다. Corner Case가 남아있었다. 

 

첫째, 다른 도시와 연결되지 않는 도시가 있는 경우. 이 경우는 도로를 통해 방문한 도시 갯수를 통해 추가적인 조건을 붙여서 간단히 해결했다.

둘째, N=1인 경우, 이것은 위의 케이스에 의해 부정되어버려서 추가적인 예외처리가 필요하다. N=1이면 그 자체로 전체 도시임에도, 도로를 통하지 않았단 이유로 -1을 출력해버리는 불상사가 발생한다.

 

이 두 케이스는 질문 게시판의 반례 덕에 찾을 수 있었다. 게시글을 남기신 분에게 감사를.

그렇게 나온 코드는 다음과 같다.

#include <iostream>
#include <vector>

using namespace std;
int eCnt = 0, N, G[51][51], gCnt = 0, cnt = 0, num = 0, ans = -1;
char ch;
bool v[2501], visited[51];
pair<int, int> dfs(int here)
{
	pair<int, int> ret = {0, 0};
	for(int i = 0; i < N; i++)
		if (G[here][i] >= 0 && !v[G[here][i]])
		{
			v[G[here][i]] = true;
			bool f = !visited[i];
			visited[i] = true;
			pair<int, int> tmp = dfs(i);
			ret = { ret.first + tmp.first + f, ret.second + tmp.second + 1};
		}
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for(int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
		{
			cin >> ch;
			if (ch == 'Y' && G[j][i] == 0) G[i][j] = ++num;
			else if (G[j][i] > 0) G[i][j] = G[j][i];
			else G[i][j] = -1;
		}
	for(int i = 0; i < N; i++)
		if (!visited[i])
		{
			visited[i] = true;
			pair<int, int> p = dfs(i);
			if (p.second == 0) continue;
			gCnt += p.first + 1;
			if (ans >= 0)
				cnt += p.second - p.first - 1;
			else
				cnt += p.second - p.first;
			++ans;
		}
	if (N == 1) cout << 0 << '\n';
	else if (gCnt < N || cnt < 0) cout << -1 << '\n';
	else cout << ans << '\n';
}

처음엔 어려워보였던 문제도 천천히 생각을 해보니 재미있는 문제가 되었다.