[백준/C++] 벌집들 (No. 3805)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 문제 이해를 잘 해야 풀 수 있는 문제였다.

 

문제를 잘 보면 벌집이 있는 곳들 사이의 경로만 존재하며, 그 경로들 중 하나가 무작위로 문제가 발생한다는 것을 알 수 있다.

 

즉, (벌집O, 벌집X)인 나무들 사이에는 경로가 없고 오로지 (벌집O, 벌집O)인 나무들 사이에만 경로가 있다는 뜻이다.

 

여기서 무작위로 하나의 경로에 문제가 생겨도 모든 나무들 사이를 이동해야한다.

 

이러한 조건을 만족하기 위해서는 내가 벌집을 만든 나무들간의 경로가 사이클을 이루어야 한다는 것을 알 수 있다.

(만약 사이클이 아니면 오로지 하나의 경로만 있는 벌집의 경로를 파괴하면 다른 벌집으로 못가는 경우가 생기게 됨)

 

이를 바탕으로 노드들 사이에 가장 작은 사이클을 찾으면 된다.

 

이때, 가장 작은 사이클을 찾기 위해서 완전 탐색으로 문제를 해결했다.

 

i번 나무를 무조건 포함하는 가장 작은 사이클을 찾고 그 사이클을 기존에 찾아진 가장 작은 사이클과 비교했다.

여기서 사이클을 찾는 방법은 i번째 나무에서 BFS로 거리를 탐색해 나가다가 기존에 방문한 적이 있는 나무가 나오면, 사이클이 존재하므로 그 값을 비교하도록 했다.

 

만약 사이클이 없으면 impossible을 출력하고 있으면 가장 작은 사이클을 만드는데 필요한 벌집의 수를 출력했다.

 

 

[아이디어 정리]

1. 조건에 맞도록 벌집을 설치하려면 나무들 사이에 사이클이 존재해야한다.
2. i번째 나무를 무조건 포함하는 사이클을 탐색해 기존에 찾은 사이클과 비교한다.
3. 이때 i번째 나무부터 BFS로 거리를 탐색해 사이클의 크기를 계산한다.

 

 

Code

 

 

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <cmath>
#include <fstream>
using namespace std;

const int INF = 987654321;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int T,N, M;
	cin >> T;
	for (int tc=1; tc<=T; tc++)
	{
		cin >> N >> M;
		int s, e;
		vector<vector<int>> v(N);
		for (int i=0; i<M; i++)
		{
			cin >> s >> e;
			v[s].push_back(e);
			v[e].push_back(s);
		}
		int minAns = INF;
		for (int t=0; t<N; t++)
		{
			queue<int> q;
			q.push(t);
			vector<int> p(N,-1);
			vector<int> dpt(N, INF);
			dpt[t] = 0;
			p[t] = t;
			int node;
			while(!q.empty())
			{
				node=q.front();
				q.pop();
				for (int i=0; i<v[node].size(); i++)
				{
					if (p[node]!=v[node][i])
					{
						if (p[v[node][i]]!=-1)
						{
							minAns = min(minAns, dpt[v[node][i]] + dpt[node]);
						}
						else
						{
							q.push(v[node][i]);
							p[v[node][i]] = node;
							dpt[v[node][i]] = dpt[node] + 1;
						}
					}
				}
			}
		}
		if (minAns==INF)
		{
			cout << "Case " << tc << ": impossible\n";
		}
		else {
			cout << "Case " << tc << ": " << minAns + 1 << "\n";
		}
	}
	return 0;
}

---

 

처음에 문제의 설명을 제대로 이해해서 벌집을 아무렇게나 지어도 되나? 계속 의문이 들었다...

문제를 제대로 이해한 후에도 풀이 방법을 떠올리기가 생각보다 힘든 문제였다...

 

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