[プログラマー]Weeklyが9週間挑戦
2453 ワード
すうれつもんだい
毎週9週間
💯 問題を解く💯
与えられた送電塔ベクトルを双方向に受信した後,すべての場合の河川で送電塔を切断し,正解を求めた.
毎週9週間
💯 問題を解く💯
与えられた送電塔ベクトルを双方向に受信した後,すべての場合の河川で送電塔を切断し,正解を求めた.
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
vector<int> graph[101];
bool visit[101];
int cnt = 0;
void cnt_parent(int idx, int a, int b){
// cout << idx << " ";
cnt ++;
for(int i = 0; i < graph[idx].size(); i++){
if(!visit[graph[idx][i]] && !((idx==a && graph[idx][i] == b) || idx==b && graph[idx][i]==a)){
visit[graph[idx][i]] = true;
cnt_parent(graph[idx][i], a, b);
visit[graph[idx][i]] = false;
}
}
}
int solution(int n, vector<vector<int>> wires) {
int answer = 10000;
for(int i = 0; i < wires.size(); i++){
int a = wires[i][0], b = wires[i][1];
graph[a].push_back(b);
graph[b].push_back(a);
}
for(int i = 0; i < wires.size(); i++){
int a = wires[i][0], b = wires[i][1];
cnt = 0;
for(int j = 0; j <= n; j++)
visit[i] = false;
visit[1] = true;
// cout << a << " " << b << "\n";
cnt_parent(1, a, b);
// cout << "\n" << "answer : " << abs(n-cnt) << "\n";
answer = min(answer, abs(cnt - abs(n - cnt)));
}
return answer;
}
Reference
この問題について([プログラマー]Weeklyが9週間挑戦), 我々は、より多くの情報をここで見つけました https://velog.io/@pkpete/프로그래머스-Week-9テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol