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

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/86971

코딩테스트 연습 - 9주차

 

약간 생각하느라 시간이 걸렸던 문제입니다.

처음에는 크루스칼 알고리즘으로 접근해야 하나? (풀었던 비슷한 문제) 하고 생각도 해 봤는데

각 전선에 별도의 가치가 존재하지 않고, 간선의 가치의 합이 아닌 노드의 개수의 차이를 최소화 하는 문제라서 이 방법으로는 실패했습니다.

 

그 다음으로 제가 시도한 방법은 전선을 하나씩 끊어 보며 dfs를 통해 탐색하는 방법입니다.

N은 최대 100이므로, 전선은 최대 99개가 존재합니다. 따라서 총 99번 동안, 각 전선을 한번씩 끊고 dfs를 돌려도 데이터의 수가 많지 않으므로 해결할 수 있습니다.

이 방법으로 성공적으로 풀었습니다.

 

	#include <string>
	#include <vector>
	#include <set>
	#include <algorithm>
	using namespace std;
	void dfs(int now, vector<set<int> > &wires, set<int> &visited) {
	for (auto &next : wires[now]) {
	if (visited.find(next) == visited.end()) {
	visited.insert(next);
	dfs(next, wires, visited);
	}
	}
	}
	int solution(int n, vector<vector<int> > wires) {
	int answer = 1e9;
	vector<set<int> > wires_adj(n+1);
	for (auto &next: wires) {
	wires_adj[next[0]].insert(next[1]);
	wires_adj[next[1]].insert(next[0]);
	}
	//n이 최대 100이므로, 선을 하나씩 끊어 보며 탐색한다.
	for (auto &next : wires) {
	//이번에 끊어볼 전선
	wires_adj[next[0]].erase(next[1]);
	wires_adj[next[1]].erase(next[0]);
	//끊은 두 전선을 시작점으로 해서 dfs를 각각 돌려본다.
	set<int> vis0, vis1;
	vis0.insert(next[0]);
	vis1.insert(next[1]);
	dfs(next[0], wires_adj, vis0);
	dfs(next[1], wires_adj, vis1);
	answer = min(answer, abs((int)vis0.size() - (int)vis1.size()));
	//끊은 전선 복구
	wires_adj[next[0]].insert(next[1]);
	wires_adj[next[1]].insert(next[0]);
	}
	return answer;
	}

view raw 전력망을 둘로 나누기.cpp hosted with ❤ by GitHub

각 dfs를 통해 방문한 노드들의 개수를 세면 되고, 노드는 중복해서 방문하지 않으므로 set을 활용하였습니다.

이번에 끊은 전선에 연결되어 있던 두 노드를 시작점으로 하고, dfs를 통해 두 개의 set에 각각 방문한 노드를 기록한 후,

set의 크기의 차의 절댓값을 계속 기록하였습니다.

끊었던 전선을 다시 잇는 것도 잊지 말아야 합니다.

 

채점 결과

이렇게 딱 풀릴 때는 기분이 너무 좋네요 ㅎㅎ