[프로그래머스 LV2] - 전력망을 둘로 나누기(트리) c++

문제

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

접근방법

input size가 100이다.

100!인 경우 절대 시간 내에 풀 수 없으므로, 

전과는 다른 방법을 사용해야 했다.

 

송전탑의 개수를 세기 위해서

dfs를 써야하나, bfs를 써야하나 고민했는데,

 

문제에 설명되어있듯이

트리를 사용하면 쉽게 풀린다.

 

f함수에서는

wires에서 하나를 삭제하고,

그에 해당하는 그래프를 find에 넘겨준다.

 

find에서

연결되어있는 송전탑의 개수를 리턴한다.

개수가 +1이 되어서 리턴하게 되는데,

차를 구하는 데에는 지장이 없어서 그냥 사용했다.

코드

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

int find(int k, vector<vector<int>> graph) {
    int sum = 1;
    for (int i=0;i<graph.size();i++) {
        if (graph[k][i]) {
            graph[k][i] = 0;
            graph[i][k] = 0;
            sum += find(i, graph);
        }
    }
    return sum;
}

int f(int r, int c, vector<vector<int>> graph) {
    graph[r][c] = 0;
    graph[c][r] = 0;
    return abs(find(r, graph) - find(c, graph));
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 10000;
    vector<vector<int>> graph(101, vector<int>(101, 0));
    
    for(vector<int> w : wires) {
        graph[w[0]][w[1]] = 1;
        graph[w[1]][w[0]] = 1;
    }
    for (int i=0;i<wires.size();i++) {
        answer = min(answer, f(wires[i][0], wires[i][1], graph));
    }
    
    return answer;
}

개선할 점

inputsize를 헷갈려 시간을 낭비했다.