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

문제 링크

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

프로그래머스

 

 

코드 구현

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> tree;
vector<bool> visited;
int nodeCount = 0;

void dfs(int node)
{
    nodeCount++;

    for (const auto& neighbor : tree[node])
    {
        if (!visited[neighbor])
        {
            visited[neighbor] = true;
            dfs(neighbor);
            visited[neighbor] = false;
        }
    }

    return;
}

int solution(int n, vector<vector<int>> wires) 
{
    tree.resize(n + 1);
    visited.resize(n + 1);

    int answer = 100;

    for (int i = 0; i < wires.size(); i++)
    {
        int node = wires[i][0];
        int neighbor = wires[i][1];
        tree[node].push_back(neighbor);
        tree[neighbor].push_back(node);
    }

    for (const auto& wire : wires)
    {
        int node1 = wire[0];
        int node2 = wire[1];

        // 연결 삭제
        tree[node1].erase(remove(tree[node1].begin(), tree[node1].end(), node2));
        tree[node2].erase(remove(tree[node2].begin(), tree[node2].end(), node1));

        // 노드 개수 세기
        nodeCount = 0;
        visited[1] = true;
        dfs(1);
        visited[1] = false;

        int diff = n - nodeCount;

        if (diff > nodeCount) diff -= nodeCount;
        else diff = nodeCount - diff;

        answer = min(answer, diff);

        // 연결 복구
        tree[node1].push_back(node2);
        tree[node2].push_back(node1);
    }


    return answer;
}

 

 

해결 방법

dfs를 이용하여 1번 노드부터 순회를 하여 연결된 지점까지의 개수를 전체 개수에서 빼면 다른 지점의 개수를 구할 수 있다. wire에 들어있는 노드 정보를 통해 하나씩 노드 연결을 끊고 노드 개수를 구하고 다시 연결을 복구시킨다.