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

 

1. 문제

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

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

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

2. 코드

#include <string>
#include <vector>

using namespace std;

//dfs, visited 방법

int graph[101][101];
int visited[101];

int dfs(int cur, int n)
{
    if(visited[cur]) return 0;      //한번 방문한 곳은 재방문 X
    int child=1;      //하위 노드의 갯수
    visited[cur]=true;
    for(int i=1;i<=n;i++)
    {
        if(graph[cur][i])       //연결, 간적 없는 곳만
        {
            child+=dfs(i,n);
        }
    }
    return child;
}

void setGraph(int x,int y,int value)
{
    graph[x][y]=value;
    graph[y][x]=value;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 101;
    
    //연결되어 있는 모든 송전탑 1로 초기화
    for(int i=0;i<wires.size();i++){
        setGraph(wires[i][0],wires[i][1],1);
    }
    
    for(int i=0;i<wires.size();i++){
        //방문 배열 초기화
        fill_n(visited,101,false);
        
        //끊을 전선 0으로 만들어주기 -> 전선 끊기
        setGraph(wires[i][0],wires[i][1],0);

        vector<int> diff;
        for(int i=1;i<=n;i++)
        {
            int tmp=dfs(i,n);       //깊이 탐색
            if(!tmp)continue;       //방문한 경우 생략
            diff.push_back(tmp);
        }
        answer = min(answer, abs(diff[0]-diff[1]));
        if(answer==0)break;
        //원상태로 돌려놓기
        setGraph(wires[i][0],wires[i][1],1);
    }
    
    return answer;
}

 

3. 해설

//dfs, visited 방법

int solution(int n, vector<vector<int>> wires) {
    int answer = 101;
    
    //연결되어 있는 모든 송전탑 1로 초기화
    for(int i=0;i<wires.size();i++){
        setGraph(wires[i][0],wires[i][1],1);
    }
    
    for(int i=0;i<wires.size();i++){
        //방문 배열 초기화
        fill_n(visited,101,false);
        
        //끊을 전선 0으로 만들어주기 -> 전선 끊기
        setGraph(wires[i][0],wires[i][1],0);

        vector<int> diff;
        for(int i=1;i<=n;i++)
        {
            int tmp=dfs(i,n);       //깊이 탐색
            if(!tmp)continue;       //방문한 경우 생략
            diff.push_back(tmp);
        }
        answer = min(answer, abs(diff[0]-diff[1]));
        if(answer==0)break;
        //원상태로 돌려놓기
        setGraph(wires[i][0],wires[i][1],1);
    }
    
    return answer;
}

dfs를 이용해서 풀어야하는 문제이다. 처음에 문제를 접근할 때 dp로 접근하여서 노드의 하위 갯수를 누적하였었는데 해당 경우는 노드가 정렬되어 있지 않을 때 적합하지 않기 때문에 사용할 수 없었다.

푸는 순서는 다음과 같습니다.

1. 먼저 연결되어 있는 모든 송전탑들을 2차원 배열에 1로 표시해줍니다.

    //연결되어 있는 모든 송전탑 1로 초기화
    for(int i=0;i<wires.size();i++){
        setGraph(wires[i][0],wires[i][1],1);
    }

2. 0~n번째 송전탑을 각각 끊는 for 문을 이용하여 n번 돌려줍니다.

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

3. 방문 배열을 초기화 해주고, 2차원 배열에서 끊을 송전탑을 0으로 만들어줍니다.

        //방문 배열 초기화
        fill_n(visited,101,false);
        
        //끊을 전선 0으로 만들어주기 -> 전선 끊기
        setGraph(wires[i][0],wires[i][1],0);

4. dfs 탐색을 통해 방문하지 않고 연결이 끊어지지 않은 곳까지 탐색을 하여 하위 노드의 갯수를 반환하고 그 값들의 차이를 반환합니다.

        vector<int> diff;
        for(int i=1;i<=n;i++)
        {
            int tmp=dfs(i,n);       //깊이 탐색
            if(!tmp)continue;       //방문한 경우 생략
            diff.push_back(tmp);
        }
        answer = min(answer, abs(diff[0]-diff[1]));
        if(answer==0)break;
        //원상태로 돌려놓기
        setGraph(wires[i][0],wires[i][1],1);