[C++][프로그래머스] 전력망을 둘로 나누기

프로그래머스

 

📄 문제

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

 

📝 풀이

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int n, vector<vector<int>> wires) {
	int answer = 101;

	vector<bool> visit(n + 1);
	vector<vector<int>> v = vector<vector<int>>(n + 1, vector<int>());
	queue<int> q;

	for (vector<int> vv : wires)
	{
		v[vv[0]].push_back(vv[1]);
		v[vv[1]].push_back(vv[0]);
	}

	for (int i = 0; i < wires.size(); ++i)
	{
		int value = 0;

		// 방문하지 않은 네트워크 노드에 방문하기
		for (int j = 1; j < visit.size(); ++j)
			if (!visit[j])
			{
				int cnt = 0;

				q.push(j);
				visit[j] = true;

				for (int n : v[j])
					if (!visit[n])
					{
						if ((wires[i][0] == j && wires[i][1] == n) || (wires[i][0] == n && wires[i][1] == j))
							continue;

						visit[n] = true;
						q.push(n);
					}

				while (!q.empty())
				{
					int from = q.front();
					q.pop();
					++cnt;

					for (int n : v[from])
						if (!visit[n])
						{
							if ((wires[i][0] == from && wires[i][1] == n) || (wires[i][0] == n && wires[i][1] == from))
								continue;

							visit[n] = true;
							q.push(n);
						}
				}

				value += value ? -cnt : +cnt;
			}

		for (int j = 1; j <= n; ++j)
			visit[j] = false;

		answer = min(answer, abs(value));
	}

	return answer;
}

• BFS를 이용하여 그래프를 방문합니다.
• 방문할 때, 출발지 <-> 목적지간 번호가 i번이 나타내는 간선일때, 해당 간선에 의한 방문은 무시한 채 노드를 방문합니다.
• 노드를 방문할 때 무조건 1회 이상은 간선이 끊겨있기때문에, 큐가 비어 빠져나올경우, 반복문을 이용하여 방문하지 않은 노드를 다시 방문하기 시작합니다. 이때, value의 값을 빼주어 이어진 노드 간 개수의 차를 구합니다.