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

문제 설명

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

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

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
    1 ≤ v1 < v2 ≤ n 입니다.
  • 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

입출력 예

n	wires	result
9	[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]	3
4	[[1,2],[2,3],[3,4]]	0
7	[[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]	1

Solution

첫 번째 입력 예제는 대충 이런식으로 되어있다는 것이다.
문제는 말이 좀 어렵긴 한데 완전탐색으로 해결 가능하다.

#include <string>
#include <vector>

using namespace std;

bool adj[101][101];
vector<bool> visited;

int DFS(int curr, const int n){
    if(visited[curr]) return 0;
    visited[curr] = true;
    int ret = 1;
    for(int i = 1; i <= n; i++){
        if(!adj[curr][i]) continue;
        ret += DFS(i, n);
    }
    return ret;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 999;
    for(int i = 0; i < wires.size(); i++){
        int u = wires[i][0];
        int v = wires[i][1];
        adj[u][v] = adj[v][u] = true;
    }

    for(int i = 0; i < wires.size(); i++){
        int u = wires[i][0];
        int v = wires[i][1];
        adj[u][v] = adj[v][u] = false;

        vector<int> count;
        visited = vector<bool>(n+1, false);
        for(int j = 1; j <= n; j++){
            int tmp = DFS(j, n);
            if(!tmp) continue;
            count.push_back(tmp);
        }
        answer = min(answer, abs(count[0]-count[1]));
        adj[u][v] = adj[v][u] = true;
    }
    return answer;
}

Solution 함수

bool adj[101][101];
vector<bool> visited;

int solution(int n, vector<vector<int>> wires) {
    int answer = 999;
    for(int i = 0; i < wires.size(); i++){
        int u = wires[i][0];
        int v = wires[i][1];
        adj[u][v] = adj[v][u] = true;
    }

    for(int i = 0; i < wires.size(); i++){
        int u = wires[i][0];
        int v = wires[i][1];
        adj[u][v] = adj[v][u] = false;

        vector<int> count;
        visited = vector<bool>(n+1, false);
        for(int j = 1; j <= n; j++){
            int tmp = DFS(j, n);
            if(!tmp) continue;
            count.push_back(tmp);
        }
        answer = min(answer, abs(count[0]-count[1]));
        adj[u][v] = adj[v][u] = true;
    }
    return answer;
}

인접 행렬 형태로 데이터를 만들어둔다. 그 후, 모든 와이어들을 하나하나 찾아보며, 그래서 얼마나 각 스팟마다 차이가 나느냐 찾아보는 문제다. 정말 단순하다.

DFS를 통해 완전탐색 문제를 해결 할 때 반드시 기억해야 하는 게 있다면, 탐색하고자 하는 곳을 탐색했으면 반드시 원상 복구를 시켜놔야 한다는 것.

어차피 DFS가 진행되면서 찾을 수 있는 곳은 다 찾을테니 와이어 하나를 끊어버리면 값은 반드시 두개보다 클 수 없다. 두 값의 차이 중 가장 작은 값을 구하면 된다.

DFS 함수

int DFS(int curr, const int n){
    if(visited[curr]) return 0;
    visited[curr] = true;
    int ret = 1;
    for(int i = 1; i <= n; i++){
        if(!adj[curr][i]) continue;
        ret += DFS(i, n);
    }
    return ret;
}

우선 인접행렬 형태로 데이터가 저장되어 있다는 사실을 꼭 기억해야 한다.
그리고 DFS기 때문에 재귀를 통해 계속해서 한 방향으로 탐색한다는 사실 또한 알아야 한다. 탐색이 되면 될 수록 ret 의 초기값은 1이므로 재귀호출이 끝나는대로 ret 에 1씩 저장될 것이다. 즉 탐색이 끝나면, 탐색 위치부터 총 N개의 와이어가 연결 되어있다는 사실을 알 수 있다.

DFS와 완전탐색 연습용으로 정말 좋은 문제다. 꼭 숙지해야 할 문제.